Logo Search packages:      
Sourcecode: wesnoth-1.7 version File versions  Download package

ca.cpp

Go to the documentation of this file.
/* $Id: ca.cpp 41353 2010-02-22 20:08:38Z boucman $ */
/*
   Copyright (C) 2009 - 2010 by Yurii Chernyi <terraninfo@terraninfo.net>
   Part of the Battle for Wesnoth Project http://www.wesnoth.org/

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License version 2
   or at your option any later version.
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY.

   See the COPYING file for more details.
*/

/**
 * Default AI (Testing)
 * @file ai/testing/ca.cpp
 */

#include "ca.hpp"
#include "../actions.hpp"
#include "../manager.hpp"
#include "../composite/engine.hpp"
#include "../composite/rca.hpp"
#include "../../foreach.hpp"
#include "../../log.hpp"
#include "../../wml_exception.hpp"

#include <numeric>

static lg::log_domain log_ai_testing_ai_default("ai/ca/testing_ai_default");
#define DBG_AI_TESTING_AI_DEFAULT LOG_STREAM(debug, log_ai_testing_ai_default)
#define LOG_AI_TESTING_AI_DEFAULT LOG_STREAM(info, log_ai_testing_ai_default)
#define WRN_AI_TESTING_AI_DEFAULT LOG_STREAM(warn, log_ai_testing_ai_default)
#define ERR_AI_TESTING_AI_DEFAULT LOG_STREAM(err, log_ai_testing_ai_default)


namespace ai {

namespace testing_ai_default {

//==============================================================

goto_phase::goto_phase( rca_context &context, const config &cfg )
      : candidate_action(context,cfg)
      , move_()
{
}

goto_phase::~goto_phase()
{
}

double goto_phase::evaluate()
{
      // Execute goto-movements - first collect gotos in a list
      std::vector<map_location> gotos;
      unit_map &units_ = get_info().units;
      gamemap &map_ = get_info().map;

      for(unit_map::iterator ui = units_.begin(); ui != units_.end(); ++ui) {
            if(ui->second.get_goto() == ui->first) {
                  ui->second.set_goto(map_location());
            } else if(ui->second.side() == get_side() && map_.on_board(ui->second.get_goto())) {
                  gotos.push_back(ui->first);
            }
      }

      for(std::vector<map_location>::const_iterator g = gotos.begin(); g != gotos.end(); ++g) {
            unit_map::const_iterator ui = units_.find(*g);
            int closest_distance = -1;
            std::pair<map_location,map_location> closest_move;
            for(move_map::const_iterator i = get_dstsrc().begin(); i != get_dstsrc().end(); ++i) {
                  if(i->second != ui->first) {
                        continue;
                  }
                  const int distance = distance_between(i->first,ui->second.get_goto());
                  if(closest_distance == -1 || distance < closest_distance) {
                        closest_distance = distance;
                        closest_move = *i;
                  }
            }

            if(closest_distance != -1) {
                  move_ = check_move_action(ui->first,closest_move.first);
                  if (move_->is_ok()) {
                        return get_score();
                  }
            }
      }

      return BAD_SCORE;
}

void goto_phase::execute()
{
      if (!move_) {
            return;
      }

      move_->execute();
      if (!move_->is_ok()){
            LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok" << std::endl;
      }
}

//==============================================================

aspect_recruitment_phase::aspect_recruitment_phase( rca_context &context, const config &cfg )
      : candidate_action(context,cfg)
{
}


aspect_recruitment_phase::~aspect_recruitment_phase()
{
}

double aspect_recruitment_phase::evaluate()
{
      const unit_map::const_iterator leader = get_info().units.find_leader(get_side());
      if(leader == get_info().units.end()) {
            return BAD_SCORE;
      }
      if(!get_info().map.is_keep(leader->first)) {
            return BAD_SCORE;
      }

      map_location recruit_loc = find_vacant_tile(get_info().map, get_info().units, leader->first, pathfind::VACANT_CASTLE);
      if (!get_info().map.on_board(recruit_loc)) {
            return BAD_SCORE;
      }

      //note that no gold check is done. This is intended, to speed up recruitment_phase::evaluate()
      //so, after 1st failed recruit, this candidate action will be blacklisted for 1 turn.

      return get_score();
}

void aspect_recruitment_phase::execute()
{
      raise_user_interact();
      stage_ptr r = get_recruitment(*this);
      if (r) {
            r->play_stage();
      } else {
            ERR_AI_TESTING_AI_DEFAULT << "no recruitment aspect - skipping recruitment" << std::endl;
      }
}

//==============================================================

recruitment_phase::recruitment_phase( rca_context &context, const config &cfg )
      : candidate_action(context,cfg)
      , unit_movement_scores_()
      , not_recommended_units_()
      , unit_combat_scores_()
{
}


recruitment_phase::~recruitment_phase()
{
}

double recruitment_phase::evaluate()
{
      const unit_map::const_iterator leader = get_info().units.find_leader(get_side());
      if(leader == get_info().units.end()) {
            return BAD_SCORE;
      }
      if(!get_info().map.is_keep(leader->first)) {
            return BAD_SCORE;
      }

      std::set<map_location> checked_hexes;
      checked_hexes.insert(leader->first);
      if(count_free_hexes_in_castle(leader->first, checked_hexes)==0) {
            return BAD_SCORE;
      }

      //note that no gold check is done. This is intended, to speed up recruitment_phase::evaluate()
      //so, after 1st failed recruit, this candidate action will be blacklisted for 1 turn.

      return get_score();
}

void recruitment_phase::execute()
{
      not_recommended_units_.clear();
      unit_combat_scores_.clear();
      unit_movement_scores_.clear();

      unit_map &units_ = get_info().units;
      gamemap &map_ = get_info().map;
      std::vector<team> &teams_ = get_info().teams;

      map_location start_pos = units_.find_leader(get_side())->first;

      raise_user_interact();
      //analyze_potential_recruit_movements();
      analyze_potential_recruit_combat();

      std::vector<std::string> options = get_recruitment_pattern();
      if (std::count(options.begin(), options.end(), "scout") > 0) {
            size_t neutral_villages = 0;

            // We recruit the initial allocation of scouts
            // based on how many neutral villages there are
            // that are closer to us than to other keeps.
            const std::vector<map_location>& villages = map_.villages();
            for(std::vector<map_location>::const_iterator v = villages.begin(); v != villages.end(); ++v) {
                  const int owner = village_owner(*v,teams_);
                  if(owner == -1) {
                        const size_t distance = distance_between(start_pos,*v);

                        bool closest = true;
                        for(std::vector<team>::const_iterator i = teams_.begin(); i != teams_.end(); ++i) {
                              const int index = i - teams_.begin() + 1;
                              const map_location& loc = map_.starting_position(index);
                              if(loc != start_pos && distance_between(loc,*v) < distance) {
                                    closest = false;
                                    break;
                              }
                        }

                        if(closest) {
                              ++neutral_villages;
                        }
                  }
            }

            // The villages per scout is for a two-side battle,
            // accounting for all neutral villages on the map.
            // We only look at villages closer to us, so we halve it,
            // making us get twice as many scouts.
            const int villages_per_scout = get_villages_per_scout()/2;

            // Get scouts depending on how many neutral villages there are.
            int scouts_wanted = villages_per_scout > 0 ? neutral_villages/villages_per_scout : 0;

            LOG_AI_TESTING_AI_DEFAULT << "scouts_wanted: " << neutral_villages << "/"
                  << villages_per_scout << " = " << scouts_wanted << "\n";

            std::map<std::string,int> unit_types;

            for(unit_map::const_iterator u = units_.begin(); u != units_.end(); ++u) {
                  if(u->second.side() == get_side()) {
                        ++unit_types[u->second.usage()];
                  }
            }

            LOG_AI_TESTING_AI_DEFAULT << "we have " << unit_types["scout"] << " scouts already and we want "
                  << scouts_wanted << " in total\n";

            while(unit_types["scout"] < scouts_wanted) {
                  if (!recruit_usage("scout")){
                        break;
                  }
                  ++unit_types["scout"];
            }
      }

      // If there is no recruitment_pattern use "" which makes us consider
      // any unit available.
      if (options.empty()) {
            options.push_back("");
      }
      // Buy units as long as we have room and can afford it.
      while (recruit_usage(options[rand()%options.size()])) {
            //refresh the recruitment pattern - it can be changed by recruit_usage
            options = get_recruitment_pattern();
            if (options.empty()) {
                  options.push_back("");
            }
      }

}

bool recruitment_phase::recruit_usage(const std::string& usage)
{
      raise_user_interact();

      const int min_gold = 0;

      log_scope2(log_ai_testing_ai_default, "recruiting troops");
      LOG_AI_TESTING_AI_DEFAULT << "recruiting '" << usage << "'\n";

      //make sure id, usage and cost are known for the coming evaluation of unit types
      unit_types.build_all(unit_type::HELP_INDEX);

      std::vector<std::string> options;
      bool found = false;
      // Find an available unit that can be recruited,
      // matches the desired usage type, and comes in under budget.
      foreach (const std::string &name, current_team().recruits())
      {
            const unit_type *ut = unit_types.find(name);
            if (!ut) continue;
            // If usage is empty consider any unit.
            if (usage.empty() || ut->usage() == usage) {
                  LOG_AI_TESTING_AI_DEFAULT << name << " considered for " << usage << " recruitment\n";
                  found = true;

                  if (current_team().gold() - ut->cost() < min_gold) {
                        LOG_AI_TESTING_AI_DEFAULT << name << " rejected, cost too high (cost: " << ut->cost() << ", current gold: " << current_team().gold() <<", min_gold: " << min_gold << ")\n";
                        continue;
                  }

                  if (not_recommended_units_.count(name))
                  {
                        LOG_AI_TESTING_AI_DEFAULT << name << " rejected, bad terrain or combat\n";
                        continue;
                  }

                  LOG_AI_TESTING_AI_DEFAULT << "recommending '" << name << "'\n";
                  options.push_back(name);
            }
      }

      // From the available options, choose one at random
      if(options.empty() == false) {
            const int option = rand()%options.size();
            recruit_result_ptr recruit_result = execute_recruit_action(options[option]);
            return recruit_result->is_ok();
      }
      if (found) {
            LOG_AI_TESTING_AI_DEFAULT << "No available units to recruit that come under the price.\n";
      } else if (usage != "") {
            //FIXME: This message should be suppressed when WML author
            //chooses the default recruitment pattern.
            const std::string warning = "At difficulty level " +
                  get_info().game_state_.classification().difficulty + ", trying to recruit a:" +
                  usage + " but no unit of that type (usage=) is"
                  " available. Check the recruit and [ai]"
                  " recruitment_pattern keys for team '" +
                  current_team().name() + "' (" +
                  lexical_cast<std::string>(get_side()) + ")"
                  " against the usage key of the"
                  " units in question! Removing invalid"
                  " recruitment_pattern entry and continuing...\n";
            WRN_AI_TESTING_AI_DEFAULT << warning;
            // Uncommented until the recruitment limiting macro can be fixed to not trigger this warning.
            //lg::wml_error << warning;
            //@fixme
            //return current_team_w().remove_recruitment_pattern_entry(usage);
            return false;
      }
      return false;
}

int recruitment_phase::average_resistance_against(const unit_type& a, const unit_type& b) const
{
      gamemap &map_ = get_info().map;

      int weighting_sum = 0, defense = 0;
      const std::map<t_translation::t_terrain, size_t>& terrain =
            map_.get_weighted_terrain_frequencies();

      for (std::map<t_translation::t_terrain, size_t>::const_iterator j = terrain.begin(),
           j_end = terrain.end(); j != j_end; ++j)
      {
            // Use only reachable tiles when computing the average defense.
        if (a.movement_type().movement_cost(map_, j->first) < unit_movement_type::UNREACHABLE) {
                  defense += a.movement_type().defense_modifier(map_, j->first) * j->second;
                  weighting_sum += j->second;
            }
      }

      if (weighting_sum == 0) {
            // This unit can't move on this map, so just get the average weighted
            // of all available terrains. This still is a kind of silly
            // since the opponent probably can't recruit this unit and it's a static unit.
            for (std::map<t_translation::t_terrain, size_t>::const_iterator jj = terrain.begin(),
                        jj_end = terrain.end(); jj != jj_end; ++jj)
            {
                  defense += a.movement_type().defense_modifier(map_, jj->first) * jj->second;
                  weighting_sum += jj->second;
            }
      }

      if(weighting_sum != 0) {
            defense /= weighting_sum;
      } else {
            ERR_AI_TESTING_AI_DEFAULT << "The weighting sum is 0 and is ignored.\n";
      }

      LOG_AI_TESTING_AI_DEFAULT << "average defense of '" << a.id() << "': " << defense << "\n";

      int sum = 0, weight_sum = 0;

      // calculation of the average damage taken
      bool steadfast = a.has_ability_by_id("steadfast");
      bool living = !a.not_living();
      const std::vector<attack_type>& attacks = b.attacks();
      for (std::vector<attack_type>::const_iterator i = attacks.begin(),
           i_end = attacks.end(); i != i_end; ++i)
      {
            int resistance = a.movement_type().resistance_against(*i);
            // Apply steadfast resistance modifier.
            if (steadfast && resistance < 100)
                  resistance = std::max<int>(resistance * 2 - 100, 50);
            // Do not look for filters or values, simply assume 70% if CTH is customized.
            int cth = i->get_special_bool("chance_to_hit", true) ? 70 : defense;
            int weight = i->damage() * i->num_attacks();
            // if cth == 0 the division will do 0/0 so don't execute this part
            if (living && cth != 0 && i->get_special_bool("poison", true)) {
                  // Compute the probability of not poisoning the unit.
                  int prob = 100;
                  for (int j = 0; j < i->num_attacks(); ++j)
                        prob = prob * (100 - cth);
                  // Assume poison works one turn.
                  weight += game_config::poison_amount * (100 - prob) / 100;
            }
            sum += cth * resistance * weight * weight; // average damage * weight
            weight_sum += weight;
      }

      // normalize by HP
      sum /= std::max<int>(1,std::min<int>(a.hitpoints(),1000)); // avoid values really out of range

      // Catch division by zero here if the attacking unit
      // has zero attacks and/or zero damage.
      // If it has no attack at all, the ai shouldn't prefer
      // that unit anyway.
      if (weight_sum == 0) {
            return sum;
      }
      return sum/weight_sum;
}

int recruitment_phase::compare_unit_types(const unit_type& a, const unit_type& b) const
{
      const int a_effectiveness_vs_b = average_resistance_against(b,a);
      const int b_effectiveness_vs_a = average_resistance_against(a,b);

      LOG_AI_TESTING_AI_DEFAULT << "comparison of '" << a.id() << " vs " << b.id() << ": "
            << a_effectiveness_vs_b << " - " << b_effectiveness_vs_a << " = "
            << (a_effectiveness_vs_b - b_effectiveness_vs_a) << '\n';
      return a_effectiveness_vs_b - b_effectiveness_vs_a;
}

void recruitment_phase::analyze_potential_recruit_combat()
{
      unit_map &units_ = get_info().units;
      if(unit_combat_scores_.empty() == false || get_recruitment_ignore_bad_combat()) {
            return;
      }

      log_scope2(log_ai_testing_ai_default, "analyze_potential_recruit_combat()");

      // Records the best combat analysis for each usage type.
      std::map<std::string,int> best_usage;

      const std::set<std::string>& recruits = current_team().recruits();
      std::set<std::string>::const_iterator i;
      for(i = recruits.begin(); i != recruits.end(); ++i) {
            const unit_type *info = unit_types.find(*i);
            if (!info || not_recommended_units_.count(*i)) {
                  continue;
            }

            int score = 0, weighting = 0;

            for(unit_map::const_iterator j = units_.begin(); j != units_.end(); ++j) {
                  if(j->second.can_recruit() || current_team().is_enemy(j->second.side()) == false) {
                        continue;
                  }

                  unit const &un = j->second;
                  const unit_type *enemy_info = unit_types.find(un.type_id());
                  VALIDATE(enemy_info, "Unknown unit type : " + un.type_id() + " while scoring units.");

                  int weight = un.cost() * un.hitpoints() / un.max_hitpoints();
                  weighting += weight;
                  score += compare_unit_types(*info, *enemy_info) * weight;
            }

            if(weighting != 0) {
                  score /= weighting;
            }

            LOG_AI_TESTING_AI_DEFAULT << "combat score of '" << *i << "': " << score << "\n";
            unit_combat_scores_[*i] = score;

            if (best_usage.count(info->usage()) == 0 ||
                        score > best_usage[info->usage()]) {
                  best_usage[info->usage()] = score;
            }
      }

      // Recommend not to use units of a certain usage type
      // if they have a score more than 600 below
      // the best unit of that usage type.
      for(i = recruits.begin(); i != recruits.end(); ++i) {
            const unit_type *info = unit_types.find(*i);
            if (!info || not_recommended_units_.count(*i)) {
                  continue;
            }

            if (unit_combat_scores_[*i] + 600 < best_usage[info->usage()]) {
                  LOG_AI_TESTING_AI_DEFAULT << "recommending not to use '" << *i << "' because of poor combat performance "
                              << unit_combat_scores_[*i] << "/" << best_usage[info->usage()] << "\n";
                  not_recommended_units_.insert(*i);
            }
      }
}


//==============================================================

combat_phase::combat_phase( rca_context &context, const config &cfg )
      : candidate_action(context,cfg),best_analysis_(),choice_rating_(-1000.0)
{
}

combat_phase::~combat_phase()
{
}

double combat_phase::evaluate()
{
      choice_rating_ = -1000.0;
      int ticks = SDL_GetTicks();

      const std::vector<attack_analysis> analysis = get_attacks();

      int time_taken = SDL_GetTicks() - ticks;
      LOG_AI_TESTING_AI_DEFAULT << "took " << time_taken << " ticks for " << analysis.size()
            << " positions. Analyzing...\n";

      ticks = SDL_GetTicks();

      const int max_sims = 50000;
      int num_sims = analysis.empty() ? 0 : max_sims/analysis.size();
      if(num_sims < 20)
            num_sims = 20;
      if(num_sims > 40)
            num_sims = 40;

      LOG_AI_TESTING_AI_DEFAULT << "simulations: " << num_sims << "\n";

      const int max_positions = 30000;
      const int skip_num = analysis.size()/max_positions;

      std::vector<attack_analysis>::const_iterator choice_it = analysis.end();
      for(std::vector<attack_analysis>::const_iterator it = analysis.begin();
                  it != analysis.end(); ++it) {

            if(skip_num > 0 && ((it - analysis.begin())%skip_num) && it->movements.size() > 1)
                  continue;

            const double rating = it->rating(get_aggression(),*this);
            LOG_AI_TESTING_AI_DEFAULT << "attack option rated at " << rating << " ("
                  << get_aggression() << ")\n";

            if(rating > choice_rating_) {
                  choice_it = it;
                  choice_rating_ = rating;
            }
      }

      time_taken = SDL_GetTicks() - ticks;
      LOG_AI_TESTING_AI_DEFAULT << "analysis took " << time_taken << " ticks\n";


      // suokko tested the rating against current_team().caution()
      // Bad mistake -- the AI became extremely reluctant to attack anything.
      // Documenting this in case someone has this bright idea again...*don't*...
      if(choice_rating_ > 0.0) {
            best_analysis_ = *choice_it;
            return get_score();
      } else {
            return BAD_SCORE;
      }
}

void combat_phase::execute()
{
      assert(choice_rating_ > 0.0);
      map_location from   = best_analysis_.movements[0].first;
      map_location to     = best_analysis_.movements[0].second;
      map_location target_loc = best_analysis_.target;

      if (from!=to) {
            move_result_ptr move_res = execute_move_action(from,to,false);
            if (!move_res->is_ok()) {
                  LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok, move failed" << std::endl;
                  return;
            }
      }

      attack_result_ptr attack_res = execute_attack_action(to, target_loc, -1);
      if (!attack_res->is_ok()) {
            LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok, attack failed" << std::endl;
      }

}

//==============================================================

move_leader_to_goals_phase::move_leader_to_goals_phase( rca_context &context, const config &cfg )
      : candidate_action(context,cfg), auto_remove_(), dst_(), id_(), move_()
{
}

move_leader_to_goals_phase::~move_leader_to_goals_phase()
{
}

double move_leader_to_goals_phase::evaluate()
{
      const config &goal = get_leader_goal();

      if (!goal) {
            LOG_AI_TESTING_AI_DEFAULT << get_name() << "No goal found\n";
            return BAD_SCORE;
      }

      if (goal.empty()) {
            LOG_AI_TESTING_AI_DEFAULT << get_name() << "Empty goal found\n";
            return BAD_SCORE;
      }

      double max_risk = lexical_cast_default<double>(goal["max_risk"],1-get_caution());
      auto_remove_ = utils::string_bool(goal["auto_remove"],false);

      dst_ = map_location(goal, &get_info().game_state_);
      if (!dst_.valid()) {
            ERR_AI_TESTING_AI_DEFAULT << "Invalid goal: "<<std::endl<<goal;
            return BAD_SCORE;
      }

      const unit_map::iterator leader = get_info().units.find_leader(get_side());
      if(!leader.valid() || leader->second.incapacitated()) {
            WRN_AI_TESTING_AI_DEFAULT << "Leader not found\n";
            return BAD_SCORE;
      }

      id_ = goal["id"];
      if (leader->first==dst_) {
            //goal already reached
            if (auto_remove_ && !id_.empty()) {
                  remove_goal(id_);
            } else {
                  move_ = check_move_action(leader->first, leader->first,!auto_remove_);//we do full moves if we don't want to remove goal
                  if (move_->is_ok()) {
                        return get_score();
                  } else {
                        return BAD_SCORE;
                  }
            }
      }

      pathfind::shortest_path_calculator calc(leader->second, current_team(), get_info().units, get_info().teams, get_info().map);
      pathfind::plain_route route = a_star_search(leader->first, dst_, 1000.0, &calc,
                  get_info().map.w(), get_info().map.h());
      if(route.steps.empty()) {
            LOG_AI_TESTING_AI_DEFAULT << "route empty";
            return BAD_SCORE;
      }

      const pathfind::paths leader_paths(get_info().map, get_info().units, leader->first,
                         get_info().teams, false, false, current_team());

      std::map<map_location,pathfind::paths> possible_moves;
      possible_moves.insert(std::pair<map_location,pathfind::paths>(leader->first,leader_paths));

      map_location loc;
      foreach (const map_location &l, route.steps)
      {
            if (leader_paths.destinations.contains(l) &&
                power_projection(l, get_enemy_dstsrc()) < double(leader->second.hitpoints())*max_risk)
            {
                  loc = l;
            }
      }

      if(loc.valid()) {
            move_ = check_move_action(leader->first,loc,false);
            if (move_->is_ok()) {
                  return get_score();
            }
      }
      return BAD_SCORE;

}

void move_leader_to_goals_phase::execute()
{
      move_->execute();
      if (!move_->is_ok()){
            LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok" << std::endl;
      }
      if (move_->get_unit_location()==dst_) {
            //goal already reached
            if (auto_remove_ && !id_.empty()) {
                  remove_goal(id_);
            }
      }
}

void move_leader_to_goals_phase::remove_goal(const std::string &id)
{
      config mod_ai;
      mod_ai["side"] = lexical_cast<std::string>(get_side());
      mod_ai["path"] = "aspect[leader_goal].facet["+id+"]";
      mod_ai["action"] = "delete";
      manager::modify_active_ai_for_side(get_side(),mod_ai);
}

//==============================================================

move_leader_to_keep_phase::move_leader_to_keep_phase( rca_context &context, const config &cfg )
      : candidate_action(context,cfg),move_()
{

}

move_leader_to_keep_phase::~move_leader_to_keep_phase()
{

}

double move_leader_to_keep_phase::evaluate()
{
      unit_map &units_ = get_info().units;
      const unit_map::iterator leader = units_.find_leader(get_side());

      if(leader == units_.end() || leader->second.incapacitated() || leader->second.movement_left()==0 ) {
            return BAD_SCORE;
      }

      // Find where the leader can move
      const pathfind::paths leader_paths(get_info().map, units_, leader->first,
             get_info().teams, false, false, current_team());
      const map_location& keep = suitable_keep(leader->first,leader_paths);

      std::map<map_location,pathfind::paths> possible_moves;
      possible_moves.insert(std::pair<map_location,pathfind::paths>(leader->first,leader_paths));

      // If the leader is not on keep, move him there.
      if(leader->first != keep) {
            if (leader_paths.destinations.contains(keep) && units_.count(keep) == 0) {
                  move_ = check_move_action(leader->first,keep,false);
                  if (move_->is_ok()){
                        return get_score();
                  }

            }
            // Make a map of the possible locations the leader can move to,
            // ordered by the distance from the keep.
            std::multimap<int,map_location> moves_toward_keep;

            // The leader can't move to his keep, try to move to the closest location
            // to the keep where there are no enemies in range.
            const int current_distance = distance_between(leader->first,keep);
            foreach (const pathfind::paths::step &dest, leader_paths.destinations)
            {
                  if (!units_.find(dest.curr).valid()){
                        const int new_distance = distance_between(dest.curr,keep);
                        if(new_distance < current_distance) {
                              moves_toward_keep.insert(std::make_pair(new_distance, dest.curr));
                        }
                  }
            }

            // Find the first location which we can move to,
            // without the threat of enemies.
            for(std::multimap<int,map_location>::const_iterator j = moves_toward_keep.begin();
                  j != moves_toward_keep.end(); ++j) {

                  if(get_enemy_dstsrc().count(j->second) == 0) {
                        move_ = check_move_action(leader->first,j->second,true);
                        if (move_->is_ok()){
                              return get_score();
                        }
                  }
            }
      }
      return BAD_SCORE;
}

void move_leader_to_keep_phase::execute()
{
      move_->execute();
      if (!move_->is_ok()){
            LOG_AI_TESTING_AI_DEFAULT <<  get_name() <<"::execute not ok" << std::endl;
      }
}

//==============================================================

get_villages_phase::get_villages_phase( rca_context &context, const config &cfg )
      : candidate_action(context,cfg)
      , keep_loc_()
      , leader_loc_()
      , best_leader_loc_()
      , debug_(false)
      , moves_()
{
}

get_villages_phase::~get_villages_phase()
{
}

double get_villages_phase::evaluate()
{
      moves_.clear();
      unit_map::const_iterator leader = get_info().units.find_leader(get_side());
      get_villages(get_possible_moves(),get_dstsrc(),get_enemy_dstsrc(),leader);
      if (moves_.size()>0) {
            return get_score();
      }
      return BAD_SCORE;
}


void get_villages_phase::execute()
{
      unit_map &units_ = get_info().units;
      unit_map::const_iterator leader = units_.find_leader(get_side());
      // Move all the units to get villages, however move the leader last,
      // so that the castle will be cleared if it wants to stop to recruit along the way.
      std::pair<map_location,map_location> leader_move;

      for(tmoves::const_iterator i = moves_.begin(); i != moves_.end(); ++i) {

            if(leader != units_.end() && leader->first == i->second) {
                  leader_move = *i;
            } else {
                  if(units_.count(i->first) == 0) {
                        move_result_ptr move_res = execute_move_action(i->second,i->first,true);
                        if (!move_res->is_ok()) {
                              return;
                        }

                        const map_location loc = move_res->get_unit_location();
                        leader = units_.find_leader(get_side());
                        const unit_map::const_iterator new_unit = units_.find(loc);

                        if(new_unit != units_.end() &&
                                    power_projection(i->first,get_enemy_dstsrc()) >= new_unit->second.hitpoints()/4) {
                              LOG_AI_TESTING_AI_DEFAULT << "found support target... " << new_unit->first << "\n";
                              //FIXME: suokko tweaked the constant 1.0 to the formula:
                              //25.0* current_team().caution() * power_projection(loc,enemy_dstsrc) / new_unit->second.hitpoints()
                              //Is this an improvement?

                              //@todo 1.7 check if this an improvement
                              //add_target(target(new_unit->first,1.0,target::SUPPORT));
                        }
                  }
            }
      }

      if(leader_move.second.valid()) {
            if(units_.count(leader_move.first) == 0 && get_info().map.is_village(leader_move.first)) {
                  move_result_ptr move_res = execute_move_action(leader_move.second,leader_move.first,true);
                  if (!move_res->is_ok()) {
                        return;
                  }
            }
      }

      return;
}

void get_villages_phase::get_villages(const moves_map& possible_moves,
            const move_map& dstsrc, const move_map& enemy_dstsrc,
            unit_map::const_iterator &leader)
{
      DBG_AI_TESTING_AI_DEFAULT << "deciding which villages we want...\n";
      unit_map &units_ = get_info().units;
      const int ticks = SDL_GetTicks();
      best_leader_loc_ = map_location::null_location;
      if(leader != units_.end()) {
            keep_loc_ = nearest_keep(leader->first);
            leader_loc_ = leader->first;
      } else {
            keep_loc_ = map_location::null_location;
            leader_loc_ = map_location::null_location;
      }

      debug_ = !lg::debug.dont_log(log_ai_testing_ai_default);

      // Find our units who can move.
      treachmap reachmap;
      for(unit_map::const_iterator u_itor = units_.begin();
                  u_itor != units_.end(); ++u_itor) {

            if(u_itor->second.side() == get_side()
                        && u_itor->second.movement_left()) {
                  reachmap.insert(std::make_pair(u_itor->first,   std::vector<map_location>()));
            }
      }


      DBG_AI_TESTING_AI_DEFAULT << reachmap.size() << " units found who can try to capture a village.\n";

      find_villages(reachmap, moves_, dstsrc, possible_moves, enemy_dstsrc);

      treachmap::iterator itor = reachmap.begin();
      while(itor != reachmap.end()) {
            if(itor->second.size() == 0) {
                  itor = remove_unit(reachmap, moves_, itor);
            } else {
                  ++itor;
            }
      }

      if(reachmap.size()) {
            DBG_AI_TESTING_AI_DEFAULT << reachmap.size() << " units left after removing the ones who "
                  "can't reach a village, send the to the dispatcher.\n";

            dump_reachmap(reachmap);

            dispatch(reachmap, moves_);
      } else {
            DBG_AI_TESTING_AI_DEFAULT << "No more units left after removing the ones who can't reach a village.\n";
      }

      LOG_AI_TESTING_AI_DEFAULT << "Village assignment done: " << (SDL_GetTicks() - ticks)
            << " ms, resulted in " << moves_.size() << " units being dispatched.\n";

}

void get_villages_phase::find_villages(
      treachmap& reachmap,
      tmoves& moves,
      const std::multimap<map_location,map_location>& dstsrc,
      const std::map<map_location,pathfind::paths>& possible_moves,
      const std::multimap<map_location,map_location>& enemy_dstsrc)

{
      std::map<map_location, double> vulnerability;

      const bool passive_leader = get_passive_leader();

      size_t min_distance = 100000;
      gamemap &map_ = get_info().map;
      std::vector<team> &teams_ = get_info().teams;

      // When a unit is dispatched we need to make sure we don't
      // dispatch this unit a second time, so store them here.
      std::vector<map_location> dispatched_units;
      for(std::multimap<map_location, map_location>::const_iterator
                  j = dstsrc.begin();
                  j != dstsrc.end(); ++j) {

            const map_location &current_loc = j->first;

            if(j->second == leader_loc_) {
                  if(passive_leader) {
                        continue;
                  }

                  const size_t distance = distance_between(keep_loc_, current_loc);
                  if(distance < min_distance) {
                        min_distance = distance;
                        best_leader_loc_ = current_loc;
                  }
            }

            if(std::find(dispatched_units.begin(), dispatched_units.end(),
                        j->second) != dispatched_units.end()) {
                  continue;
            }

            if(map_.is_village(current_loc) == false) {
                  continue;
            }

            bool want_village = true, owned = false;
            for(size_t n = 0; n != teams_.size(); ++n) {
                  owned = teams_[n].owns_village(current_loc);
                  if(owned && !current_team().is_enemy(n+1)) {
                        want_village = false;
                  }

                  if(owned) {
                        break;
                  }
            }

            if(want_village == false) {
                  continue;
            }

            // If it is a neutral village, and we have no leader,
            // then the village is of no use to us, and we don't want it.
            if(!owned && leader_loc_ == map_location::null_location) {
                  continue;
            }

            // If we have a decent amount of gold, and the leader can't access
            // the keep this turn if they get this village,
            // then don't get this village with them.
            if(want_village &&
                        current_team().gold() > 20 &&
                        leader_loc_ == current_loc &&
                        leader_loc_ != keep_loc_ &&
                        multistep_move_possible(j->second, current_loc, keep_loc_, possible_moves) == false) {
                  continue;
            }

            double threat = 0.0;
            const std::map<map_location,double>::const_iterator vuln = vulnerability.find(current_loc);
            if(vuln != vulnerability.end()) {
                  threat = vuln->second;
            } else {
                  threat = power_projection(current_loc,enemy_dstsrc);
                  vulnerability.insert(std::pair<map_location,double>(current_loc,threat));
            }

            const unit_map::const_iterator u = get_info().units.find(j->second);
            if (u == get_info().units.end() || u->second.get_state("guardian")) {
                  continue;
            }

            const unit& un = u->second;
            //FIXME: suokko turned this 2:1 to 1.5:1.0.
            //and dropped the second term of the multiplication.  Is that better?
            //const double threat_multipler = (current_loc == leader_loc?2:1) * current_team().caution() * 10;
            if(un.hitpoints() < (threat*2*un.defense_modifier(map_.get_terrain(current_loc)))/100) {
                  continue;
            }

            // If the next and previous destination differs from our current destination,
            // we're the only one who can reach the village -> dispatch.
            std::multimap<map_location, map_location>::const_iterator next = j;
            ++next; // j + 1 fails
            const bool at_begin = (j == dstsrc.begin());
            std::multimap<map_location, map_location>::const_iterator prev = j; //FIXME seems not to work
            if(!at_begin) {
                  --prev;
            }
#if 1
            if((next == dstsrc.end() || next->first != current_loc)
                        && (at_begin || prev->first != current_loc)) {

                  move_result_ptr move_check_res = check_move_action(j->second,j->first,true);
                  if (move_check_res->is_ok()) {
                        DBG_AI_TESTING_AI_DEFAULT << "Dispatched unit at " << j->second << " to village " << j->first << '\n';
                        moves.push_back(std::make_pair(j->first, j->second));
                  }
                  reachmap.erase(j->second);
                  dispatched_units.push_back(j->second);
                  continue;
            }
#endif
            reachmap[j->second].push_back(current_loc);
      }

      DBG_AI_TESTING_AI_DEFAULT << moves.size() << " units already dispatched, "
            << reachmap.size() << " left to evaluate.\n";
}

void get_villages_phase::dispatch(treachmap& reachmap, tmoves& moves)
{
      DBG_AI_TESTING_AI_DEFAULT << "Starting simple dispatch.\n";

      // we now have a list with units with the villages they can reach.
      // keep trying the following steps as long as one of them changes
      // the state.
      // 1. Dispatch units who can reach 1 village (if more units can reach that
      //    village only one can capture it, so use the first in the list.)
      // 2. Villages which can only be reached by one unit get that unit dispatched
      //    to them.
      size_t village_count = 0;
      bool dispatched = true;
      while(dispatched) {
            dispatched = false;

            if(dispatch_unit_simple(reachmap, moves)) {
                  dispatched = true;
            } else {
                  if(reachmap.empty()) {
                        DBG_AI_TESTING_AI_DEFAULT << "dispatch_unit_simple() found a final solution.\n";
                        break;
                  } else {
                        DBG_AI_TESTING_AI_DEFAULT << "dispatch_unit_simple() couldn't dispatch more units.\n";
                  }
            }

            if(dispatch_village_simple(reachmap, moves, village_count)) {
                  dispatched = true;
            } else {
                  if(reachmap.empty()) {
                        DBG_AI_TESTING_AI_DEFAULT << "dispatch_village_simple() found a final solution.\n";
                        break;
                  } else {
                        DBG_AI_TESTING_AI_DEFAULT << "dispatch_village_simple() couldn't dispatch more units.\n";
                  }
            }

            if(reachmap.size() != 0 && dispatched) {
                  DBG_AI_TESTING_AI_DEFAULT << reachmap.size() << " unit(s) left restarting simple dispatching.\n";

                  dump_reachmap(reachmap);
            }
      }

      if(reachmap.size() == 0) {
            DBG_AI_TESTING_AI_DEFAULT << "No units left after simple dispatcher.\n";
            return;
      }

      DBG_AI_TESTING_AI_DEFAULT << reachmap.size() << " units left for complex dispatch with "
            << village_count << " villages left.\n";

      dump_reachmap(reachmap);

      dispatch_complex(reachmap, moves, village_count);
}

// Returns        need further processing
// false          Nothing has been modified or no units left
bool get_villages_phase::dispatch_unit_simple(treachmap& reachmap, tmoves& moves)
{
      bool result = false;

      treachmap::iterator itor = reachmap.begin();
      while(itor != reachmap.end()) {
            if(itor->second.size() == 1) {
                  const map_location village = itor->second[0];
                  result = true;

                  DBG_AI_TESTING_AI_DEFAULT << "Dispatched unit at " << itor->first << " to village " << village << '\n';
                  moves.push_back(std::make_pair(village, itor->first));
                  reachmap.erase(itor++);

                  if(remove_village(reachmap, moves, village)) {
                        itor = reachmap.begin();
                  }

            } else {
                  ++itor;
            }
      }

      // Test special cases.
      if(reachmap.empty()) {
            // We're done.
            return false;
      }

      if(reachmap.size() == 1) {
            // One unit left.
            DBG_AI_TESTING_AI_DEFAULT << "Dispatched _last_ unit at " << reachmap.begin()->first
                  << " to village " << reachmap.begin()->second[0] << '\n';

            moves.push_back(std::make_pair(
                  reachmap.begin()->second[0], reachmap.begin()->first));

            reachmap.clear();
            // We're done.
            return false;
      }

      return result;
}

bool get_villages_phase::dispatch_village_simple(
      treachmap& reachmap, tmoves& moves, size_t& village_count)
{

      bool result = false;
      bool dispatched = true;
      while(dispatched) {
            dispatched = false;

            // build the reverse map
            std::map<map_location /*village location*/,
                  std::vector<map_location /* units that can reach it*/> >reversemap;

            treachmap::const_iterator itor = reachmap.begin();
            for(;itor != reachmap.end(); ++itor) {

                  for(std::vector<map_location>::const_iterator
                              v_itor = itor->second.begin();
                              v_itor != itor->second.end(); ++v_itor) {

                        reversemap[*v_itor].push_back(itor->first);

                  }
            }

            village_count = reversemap.size();

            itor = reversemap.begin();
            while(itor != reversemap.end()) {
                  if(itor->second.size() == 1) {
                        // One unit can reach this village.
                        const map_location village = itor->first;
                        dispatched = true;
                        result = true;

                        DBG_AI_TESTING_AI_DEFAULT << "Dispatched unit at " << itor->second[0] << " to village " << itor->first << '\n';
                        moves.push_back(std::make_pair(itor->first, itor->second[0]));

                        reachmap.erase(itor->second[0]);
                        remove_village(reachmap, moves, village);
                        // Get can go to some trouble to remove the unit from the other villages
                        // instead we abort this loop end do a full rebuild on the map.
                        break;
                  } else {
                        ++itor;
                  }
            }
      }

      return result;
}

bool get_villages_phase::remove_village(
      treachmap& reachmap, tmoves& moves, const map_location& village)
{
      bool result = false;
      treachmap::iterator itor = reachmap.begin();
      while(itor != reachmap.end()) {
            itor->second.erase(std::remove(itor->second.begin(), itor->second.end(), village), itor->second.end());
            if(itor->second.empty()) {
                  result = true;
                  itor = remove_unit(reachmap, moves, itor);
            } else {
                  ++itor;
            }
      }
      return result;
}

get_villages_phase::treachmap::iterator get_villages_phase::remove_unit(
      treachmap& reachmap, tmoves& moves, treachmap::iterator unit)
{
      assert(unit->second.empty());

      if(unit->first == leader_loc_ && best_leader_loc_ != map_location::null_location) {
            DBG_AI_TESTING_AI_DEFAULT << "Dispatch leader at " << leader_loc_ << " closer to the keep at "
                  << best_leader_loc_ << '\n';

            moves.push_back(std::make_pair(best_leader_loc_, leader_loc_));
      }

      reachmap.erase(unit++);
      return unit;
}

void get_villages_phase::dispatch_complex(
      treachmap& reachmap, tmoves& moves, const size_t village_count)
{
      // ***** ***** Init and dispatch if every unit can reach every village.

      const size_t unit_count = reachmap.size();
      // The maximum number of villages we can capture with the available units.
      const size_t max_result = unit_count < village_count ? unit_count : village_count;

      assert(unit_count >= 2 && village_count >= 2);

      // Every unit can reach every village.
      if(unit_count == 2 && village_count == 2) {
            DBG_AI_TESTING_AI_DEFAULT << "Every unit can reach every village for 2 units, dispatch them.\n";
            full_dispatch(reachmap, moves);
            return;
      }

      std::vector<map_location> units(unit_count);
      std::vector<size_t> villages_per_unit(unit_count);
      std::vector<map_location> villages;
      std::vector<size_t> units_per_village(village_count);

      // We want to test the units, the ones who can reach the least
      // villages first so this is our lookup map.
      std::multimap<size_t /* villages_per_unit value*/,
            size_t /*villages_per_unit index*/> unit_lookup;

      std::vector</*unit*/std::vector</*village*/bool> >
            matrix(reachmap.size(), std::vector<bool>(village_count, false));

      treachmap::const_iterator itor = reachmap.begin();
      for(size_t u = 0; u < unit_count; ++u, ++itor) {
            units[u] = itor->first;
            villages_per_unit[u] = itor->second.size();
            unit_lookup.insert(std::make_pair(villages_per_unit[u], u));

            assert(itor->second.size() >= 2);

            for(size_t v = 0; v < itor->second.size(); ++v) {

                  size_t v_index;
                  // find the index of the v in the villages
                  std::vector<map_location>::const_iterator v_itor =
                        std::find(villages.begin(), villages.end(), itor->second[v]);
                  if(v_itor == villages.end()) {
                        v_index = villages.size(); // will be the last element after push_back.
                        villages.push_back(itor->second[v]);
                  } else {
                        v_index = v_itor - villages.begin();
                  }

                  units_per_village[v_index]++;

                  matrix[u][v_index] = true;
            }
      }
      for(std::vector<size_t>::const_iterator upv_it = units_per_village.begin();
                  upv_it != units_per_village.end(); ++upv_it) {

            assert(*upv_it >=2);
      }

      if(debug_) {
            // Print header
            std::cerr << "Reach matrix:\n\nvillage";
            size_t u, v;
            for(v = 0; v < village_count; ++v) {
                  std::cerr << '\t' << villages[v];
            }
            std::cerr << "\ttotal\nunit\n";

            // Print data
            for(u = 0; u < unit_count; ++u) {
                  std::cerr << units[u];

                  for(size_t v = 0; v < village_count; ++v) {
                        std::cerr << '\t' << matrix[u][v];
                  }
                  std::cerr << "\t" << villages_per_unit[u] << '\n';
            }

            // Print footer
            std::cerr << "total";
            for(v = 0; v < village_count; ++v) {
                  std::cerr << '\t' << units_per_village[v];
            }
            std::cerr << '\n';
      }

      // Test the special case, everybody can reach all villages
      const bool reach_all = ((village_count == unit_count)
            && (std::accumulate(villages_per_unit.begin(), villages_per_unit.end(), size_t())
            == (village_count * unit_count)));

      if(reach_all) {
            DBG_AI_TESTING_AI_DEFAULT << "Every unit can reach every village, dispatch them\n";
            full_dispatch(reachmap, moves);
            reachmap.clear();
            return;
      }

      // ***** ***** Find a square
      std::multimap<size_t /* villages_per_unit value*/, size_t /*villages_per_unit index*/>
            ::const_iterator src_itor =  unit_lookup.begin();

      while(src_itor != unit_lookup.end() && src_itor->first == 2) {

            for(std::multimap<size_t, size_t>::const_iterator
                        dst_itor = unit_lookup.begin();
                        dst_itor != unit_lookup.end(); ++ dst_itor) {

                  // avoid comparing us with ourselves.
                  if(src_itor == dst_itor) {
                        continue;
                  }

                  std::vector<bool> result;
                  std::transform(matrix[src_itor->second].begin(), matrix[src_itor->second].end(),
                        matrix[dst_itor->second].begin(),
                        std::back_inserter(result),
                        std::logical_and<bool>()
                        );

                  size_t matched = std::count(result.begin(), result.end(), true);

                  // we found a  solution, dispatch
                  if(matched == 2) {
                        // Collect data
                        std::vector<bool>::iterator first = std::find(result.begin(), result.end(), true);
                        std::vector<bool>::iterator second = std::find(first + 1, result.end(), true);

                        const map_location village1 = villages[first - result.begin()];
                        const map_location village2 = villages[second - result.begin()];

                        const bool perfect = (src_itor->first == 2 &&
                              dst_itor->first == 2 &&
                              units_per_village[first - result.begin()] == 2 &&
                              units_per_village[second - result.begin()] == 2);

                        // Dispatch
                        DBG_AI_TESTING_AI_DEFAULT << "Found a square.\nDispatched unit at " << units[src_itor->second]
                                    << " to village " << village1 << '\n';
                        moves.push_back(std::make_pair(village1, units[src_itor->second]));

                        DBG_AI_TESTING_AI_DEFAULT << "Dispatched unit at " << units[dst_itor->second]
                                    << " to village " << village2 << '\n';
                        moves.push_back(std::make_pair(village2, units[dst_itor->second]));

                        // Remove the units
                        reachmap.erase(units[src_itor->second]);
                        reachmap.erase(units[dst_itor->second]);

                        // Evaluate and start correct function.
                        if(perfect) {
                              // We did a perfect dispatch 2 units who could visit 2 villages.
                              // This means we didn't change the assertion for this funtions
                              // so call ourselves recursively, and finish afterwards.
                              DBG_AI_TESTING_AI_DEFAULT << "Perfect dispatch, do complex again.\n";
                              dispatch_complex(reachmap, moves, village_count - 2);
                              return;
                        } else {
                              // We did a not perfect dispatch but we did modify things
                              // so restart dispatching.
                              DBG_AI_TESTING_AI_DEFAULT << "NON Perfect dispatch, do dispatch again.\n";
                              remove_village(reachmap, moves, village1);
                              remove_village(reachmap, moves, village2);
                              dispatch(reachmap, moves);
                              return;
                        }
                  }
            }

            ++src_itor;
      }

      // ***** ***** Do all permutations.
      // Now walk through all possible permutations
      // - test whether the suggestion is possible
      // - does it result in max_villages
      //   - dispatch and ready
      // - is it's result better as the last best
      //   - store
      std::vector<std::pair<map_location, map_location> > best_result;

      // Bruteforcing all possible permutations can result in a slow game.
      // So there needs to be a balance between the best possible result and
      // not too slow. From the test (at the end of the file) a good number is
      // picked. In general we shouldn't reach this point too often if we do
      // there are a lot of villages which are unclaimed and a lot of units
      // to claim them.
      const size_t max_options = 8;
      if(unit_count >= max_options && village_count >= max_options) {

            DBG_AI_TESTING_AI_DEFAULT << "Too many units " << unit_count << " and villages "
                  << village_count<<" found, evaluate only the first "
                  << max_options << " options;\n";

            std::vector<size_t> perm (max_options, 0);
            for(size_t i =0; i < max_options; ++i) {
                  perm[i] = i;
            }
            while(std::next_permutation(perm.begin(), perm.end())) {

                  // Get result for current permutation.
                  std::vector<std::pair<map_location,map_location> > result;
                  for(size_t u = 0; u < max_options; ++u) {
                        if(matrix[u][perm[u]]) {
                              result.push_back(std::make_pair(villages[perm[u]], units[u]));

                        }
                  }
                  if(result.size() == max_result) {
                        best_result.swap(result);
                        break;
                  }

                  if(result.size() > best_result.size()) {
                        best_result.swap(result);
                  }
            }
            // End of loop no optimal found, assign the best
            std::copy(best_result.begin(), best_result.end(), std::back_inserter(moves));

            // Clean up the reachmap for dispatched units.
            for(std::vector<std::pair<map_location, map_location> >::const_iterator
                        itor = best_result.begin(); itor != best_result.end(); ++itor) {
                  reachmap.erase(itor->second);
            }

            // Try to dispatch whatever is left
            dispatch(reachmap, moves);
            return;

      } else if(unit_count <= village_count) {

            DBG_AI_TESTING_AI_DEFAULT << "Unit major\n";

            std::vector<size_t> perm (unit_count, 0);
            for(size_t i =0; i < unit_count; ++i) {
                  perm[i] = i;
            }
            while(std::next_permutation(perm.begin(), perm.end())) {
                  // Get result for current permutation.
                  std::vector<std::pair<map_location,map_location> > result;
                  for(size_t u = 0; u < unit_count; ++u) {
                        if(matrix[u][perm[u]]) {
                              result.push_back(std::make_pair(villages[perm[u]], units[u]));

                        }
                  }
                  if(result.size() == max_result) {
                        std::copy(result.begin(), result.end(), std::back_inserter(moves));
                        reachmap.clear();
                        return;
                  }

                  if(result.size() > best_result.size()) {
                        best_result.swap(result);
                  }
            }
            // End of loop no optimal found, assign the best
            std::copy(best_result.begin(), best_result.end(), std::back_inserter(moves));

            // clean up the reachmap we need to test whether the leader is still there
            // and if so remove him manually to get him dispatched.
            for(std::vector<std::pair<map_location, map_location> >::const_iterator
                        itor = best_result.begin(); itor != best_result.end(); ++itor) {
                  reachmap.erase(itor->second);
            }
            treachmap::iterator unit = reachmap.find(leader_loc_);
            if(unit != reachmap.end()) {
                  unit->second.clear();
                  remove_unit(reachmap, moves, unit);
            }
            reachmap.clear();

      } else {

            DBG_AI_TESTING_AI_DEFAULT << "Village major\n";

            std::vector<size_t> perm (village_count, 0);
            for(size_t i =0; i < village_count; ++i) {
                  perm[i] = i;
            }
            while(std::next_permutation(perm.begin(), perm.end())) {
                  // Get result for current permutation.
                  std::vector<std::pair<map_location,map_location> > result;
                  for(size_t v = 0; v < village_count; ++v) {
                        if(matrix[perm[v]][v]) {
                              result.push_back(std::make_pair(villages[v], units[perm[v]]));

                        }
                  }
                  if(result.size() == max_result) {
                        std::copy(result.begin(), result.end(), std::back_inserter(moves));
                        reachmap.clear();
                        return;
                  }

                  if(result.size() > best_result.size()) {
                        best_result.swap(result);
                  }
            }
            // End of loop no optimal found, assigne the best
            std::copy(best_result.begin(), best_result.end(), std::back_inserter(moves));

            // clean up the reachmap we need to test whether the leader is still there
            // and if so remove him manually to get him dispatched.
            for(std::vector<std::pair<map_location, map_location> >::const_iterator
                        itor = best_result.begin(); itor != best_result.end(); ++itor) {
                  reachmap.erase(itor->second);
            }
            treachmap::iterator unit = reachmap.find(leader_loc_);
            if(unit != reachmap.end()) {
                  unit->second.clear();
                  remove_unit(reachmap, moves, unit);
            }
            reachmap.clear();
      }
}

void get_villages_phase::full_dispatch(treachmap& reachmap, tmoves& moves)
{
      treachmap::const_iterator itor = reachmap.begin();
      for(size_t i = 0; i < reachmap.size(); ++i, ++itor) {
            DBG_AI_TESTING_AI_DEFAULT << "Dispatched unit at " << itor->first
                        << " to village " << itor->second[i] << '\n';
            moves.push_back(std::make_pair(itor->second[i], itor->first));
      }
}

void get_villages_phase::dump_reachmap(treachmap& reachmap)
{
      if(!debug_) {
            return;
      }

      for(treachmap::const_iterator itor =
                  reachmap.begin(); itor != reachmap.end(); ++itor) {

            std::cerr << "Reachlist for unit at " << itor->first;

            if(itor->second.empty()) {
                  std::cerr << "\tNone";
            }

            for(std::vector<map_location>::const_iterator
                        v_itor = itor->second.begin();
                        v_itor != itor->second.end(); ++v_itor) {

                  std::cerr << '\t' << *v_itor;
            }
            std::cerr << '\n';

      }
}

//==============================================================

get_healing_phase::get_healing_phase( rca_context &context, const config &cfg )
      : candidate_action(context,cfg),move_()
{
}

get_healing_phase::~get_healing_phase()
{
}

double get_healing_phase::evaluate()
{
      // Find units in need of healing.
      unit_map &units_ = get_info().units;
      unit_map::iterator u_it = units_.begin();
      for(; u_it != units_.end(); ++u_it) {
            unit& u = u_it->second;

            // If the unit is on our side, has lost as many or more than
            // 1/2 round worth of healing, and doesn't regenerate itself,
            // then try to find a vacant village for it to rest in.
            if(u.side() == get_side() &&
               (u.max_hitpoints() - u.hitpoints() >= game_config::poison_amount/2
               || u.get_state(unit::STATE_POISONED)) &&
                !u.get_ability_bool("regenerate"))
            {
                  // Look for the village which is the least vulnerable to enemy attack.
                  typedef std::multimap<map_location,map_location>::const_iterator Itor;
                  std::pair<Itor,Itor> it = get_srcdst().equal_range(u_it->first);
                  double best_vulnerability = 100000.0;
                  // Make leader units more unlikely to move to vulnerable villages
                  const double leader_penalty = (u.can_recruit()?2.0:1.0);
                  Itor best_loc = it.second;
                  while(it.first != it.second) {
                        const map_location& dst = it.first->second;
                        if(get_info().map.gives_healing(dst) && (units_.find(dst) == units_.end() || dst == u_it->first)) {
                              const double vuln = power_projection(it.first->first, get_enemy_dstsrc());
                              DBG_AI_TESTING_AI_DEFAULT << "found village with vulnerability: " << vuln << "\n";
                              if(vuln < best_vulnerability) {
                                    best_vulnerability = vuln;
                                    best_loc = it.first;
                                    DBG_AI_TESTING_AI_DEFAULT << "chose village " << dst << '\n';
                              }
                        }

                        ++it.first;
                  }

                  // If we have found an eligible village,
                  // and we can move there without expecting to get whacked next turn:
                  if(best_loc != it.second && best_vulnerability*leader_penalty < u.hitpoints()) {
                        move_ = check_move_action(best_loc->first,best_loc->second,true);
                        if (move_->is_ok()) {
                              return get_score();
                        }
                  }
            }
      }

      return BAD_SCORE;
}

void get_healing_phase::execute()
{
      LOG_AI_TESTING_AI_DEFAULT << "moving unit to village for healing...\n";
      move_->execute();
      if (!move_->is_ok()){
            LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok" << std::endl;
      }
}

//==============================================================

retreat_phase::retreat_phase( rca_context &context, const config &cfg )
      : candidate_action(context,cfg), move_()
{
}

retreat_phase::~retreat_phase()
{
}

double retreat_phase::evaluate()
{


      // Get versions of the move map that assume that all units are at full movement
      unit_map units_ = get_info().units;

      unit_map::const_iterator leader = units_.find_leader(get_side());
      std::map<map_location,pathfind::paths> dummy_possible_moves;

      move_map fullmove_srcdst;
      move_map fullmove_dstsrc;
      calculate_possible_moves(dummy_possible_moves, fullmove_srcdst, fullmove_dstsrc,
                  false, true, &get_avoid());

      map_location leader_adj[6];
      if(leader != units_.end()) {
            get_adjacent_tiles(leader->first,leader_adj);
      }

      for(unit_map::iterator i = units_.begin(); i != units_.end(); ++i) {
            if(i->second.side() == get_side() &&
                        i->second.movement_left() == i->second.total_movement() &&
                        unit_map::const_iterator(i) != leader &&
                        !i->second.incapacitated()) {

                  // This unit still has movement left, and is a candidate to retreat.
                  // We see the amount of power of each side on the situation,
                  // and decide whether it should retreat.
                  if(should_retreat(i->first, i, fullmove_srcdst, fullmove_dstsrc, get_caution())) {

                        bool can_reach_leader = false;

                        // Time to retreat. Look for the place where the power balance
                        // is most in our favor.
                        // If we can't find anywhere where we like the power balance,
                        // just try to get to the best defensive hex.
                        typedef move_map::const_iterator Itor;
                        std::pair<Itor,Itor> itors = get_srcdst().equal_range(i->first);
                        map_location best_pos, best_defensive(i->first);

                        double best_rating = -1000.0;
                        int best_defensive_rating = i->second.defense_modifier(get_info().map.get_terrain(i->first))
                              - (get_info().map.is_village(i->first) ? 10 : 0);
                        while(itors.first != itors.second) {

                              if(leader != units_.end() && std::count(leader_adj,
                                                leader_adj + 6, itors.first->second)) {

                                    can_reach_leader = true;
                                    break;
                              }

                              // We rate the power balance of a hex based on our power projection
                              // compared to theirs, multiplying their power projection by their
                              // chance to hit us on the hex we're planning to flee to.
                              const map_location& hex = itors.first->second;
                              const int defense = i->second.defense_modifier(get_info().map.get_terrain(hex));
                              const double our_power = power_projection(hex,get_dstsrc());
                              const double their_power = power_projection(hex,get_enemy_dstsrc()) * double(defense)/100.0;
                              const double rating = our_power - their_power;
                              if(rating > best_rating) {
                                    best_pos = hex;
                                    best_rating = rating;
                              }

                              // Give a bonus for getting to a village.
                              const int modified_defense = defense - (get_info().map.is_village(hex) ? 10 : 0);

                              if(modified_defense < best_defensive_rating) {
                                    best_defensive_rating = modified_defense;
                                    best_defensive = hex;
                              }

                              ++itors.first;
                        }

                        // If the unit is in range of its leader, it should
                        // never retreat -- it has to defend the leader instead.
                        if(can_reach_leader) {
                              continue;
                        }

                        if(!best_pos.valid()) {
                              best_pos = best_defensive;
                        }

                        if(best_pos.valid()) {
                              move_ = check_move_action(i->first,best_pos,true);
                              if (move_->is_ok()) {
                                    return get_score();
                              }
                        }
                  }
            }
      }

      return BAD_SCORE;
}

void retreat_phase::execute()
{
      move_->execute();
      if (!move_->is_ok()){
            LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok" << std::endl;
      }
}



bool retreat_phase::should_retreat(const map_location& loc, const unit_map::const_iterator& un,  const move_map &srcdst, const move_map &dstsrc, double caution)
{
      const move_map &enemy_dstsrc = get_enemy_dstsrc();

      if(caution <= 0.0) {
            return false;
      }

      const double optimal_terrain = best_defensive_position(un->first, dstsrc,
                  srcdst, enemy_dstsrc).chance_to_hit/100.0;
      const double proposed_terrain =
            un->second.defense_modifier(get_info().map.get_terrain(loc))/100.0;

      // The 'exposure' is the additional % chance to hit
      // this unit receives from being on a sub-optimal defensive terrain.
      const double exposure = proposed_terrain - optimal_terrain;

      const double our_power = power_projection(loc,dstsrc);
      const double their_power = power_projection(loc,enemy_dstsrc);
      return caution*their_power*(1.0+exposure) > our_power;
}


//==============================================================

simple_move_and_targeting_phase::simple_move_and_targeting_phase(
            rca_context &context, const config &cfg)
      : candidate_action(context,cfg)
      , move_()
{
}

simple_move_and_targeting_phase::~simple_move_and_targeting_phase()
{
}

double simple_move_and_targeting_phase::evaluate()
{
      unit_map &units_ = get_info().units;

      unit_map::const_iterator leader = units_.find_leader(get_side());
      map_location my_leader_loc = map_location::null_location;
      if (leader.valid()) {
            my_leader_loc = leader->first;
      }

      for(leader = units_.begin(); leader != units_.end(); ++leader) {
            if(leader->second.can_recruit() && current_team().is_enemy(leader->second.side())) {
                  break;
            }
      }

      if(leader == units_.end()) {
            return BAD_SCORE;
      }

      int closest_distance = -1;
      std::pair<map_location,map_location> closest_move;

      for(move_map::const_iterator i = get_dstsrc().begin(); i != get_dstsrc().end(); ++i) {
            const int distance = distance_between(i->first,leader->first);
            if(closest_distance == -1 || distance < closest_distance) {
                  if ((i->second!=my_leader_loc) && (i->second!=i->first)) {
                        closest_distance = distance;
                        closest_move = *i;
                  }
            }
      }

      if(closest_distance != -1) {
            move_ = check_move_action(closest_move.second,closest_move.first,true);
            if (move_->is_ok()){
                  return get_score();
            }
      }

      return BAD_SCORE;
}

void simple_move_and_targeting_phase::execute()
{
      move_->execute();
      if (!move_->is_ok()){
            LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok" << std::endl;
      }
}


//==============================================================

leader_control_phase::leader_control_phase( rca_context &context, const config &cfg )
      : candidate_action(context,cfg)
{
}


leader_control_phase::~leader_control_phase()
{
}

double leader_control_phase::evaluate()
{
      ERR_AI_TESTING_AI_DEFAULT << get_name() << ": evaluate - not yet implemented" << std::endl;
      return BAD_SCORE;
}



void leader_control_phase::execute()
{
      ERR_AI_TESTING_AI_DEFAULT << get_name() << ": execute - not yet implemented" << std::endl;
}

//==============================================================

} //end of namespace testing_ai_default

} //end of namespace ai

Generated by  Doxygen 1.6.0   Back to index