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

ca.cpp

Go to the documentation of this file.
/* $Id: ca.cpp 46186 2010-09-01 21:12:38Z silene $ */
/*
   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 as published by
   the Free Software Foundation; either version 2 of the License, 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
 */

#include "ca.hpp"
#include "../actions.hpp"
#include "../manager.hpp"
#include "../composite/engine.hpp"
#include "../composite/rca.hpp"
#include "../composite/stage.hpp"
#include "../../gamestatus.hpp"
#include "../../foreach.hpp"
#include "../../log.hpp"
#include "../../map.hpp"
#include "../../resources.hpp"
#include "../../team.hpp"
#include "../../wml_exception.hpp"
#include "../../pathfind/pathfind.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_ = *resources::units;
      gamemap &map_ = *resources::game_map;

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

      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->get_location()) {
                        continue;
                  }
                  int distance = distance_between(i->first,ui->get_goto());
                  if(closest_distance == -1 || distance < closest_distance) {
                        closest_distance = distance;
                        closest_move = *i;
                  }
            }

            if(closest_distance != -1) {
                  move_ = check_move_action(ui->get_location(), 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 = resources::units->find_leader(get_side());
      if(leader == resources::units->end()) {
            return BAD_SCORE;
      }
      if (!resources::game_map->is_keep(leader->get_location())) {
            return BAD_SCORE;
      }

      map_location recruit_loc = find_vacant_tile(*resources::game_map, *resources::units, leader->get_location(), pathfind::VACANT_CASTLE);
      if (!resources::game_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 = resources::units->find_leader(get_side());
      if(leader == resources::units->end()) {
            return BAD_SCORE;
      }
      if (!resources::game_map->is_keep(leader->get_location())) {
            return BAD_SCORE;
      }

      std::set<map_location> checked_hexes;
      checked_hexes.insert(leader->get_location());
      if (count_free_hexes_in_castle(leader->get_location(), 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_ = *resources::units;
      gamemap &map_ = *resources::game_map;
      std::vector<team> &teams_ = *resources::teams;

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

      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->side() == get_side()) {
                        ++unit_types[u->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 " +
                  resources::state_of_game->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_ = *resources::game_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_ = *resources::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->can_recruit() || !current_team().is_enemy(j->side())) {
                        continue;
                  }

                  unit const &un = *j;
                  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 = check_attack_action(to, target_loc, -1);
      if (!attack_res->is_ok()) {
            LOG_AI_TESTING_AI_DEFAULT << get_name() << "::execute not ok, attack cancelled" << std::endl;
      } else {
            attack_res->execute();
            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 = goal["max_risk"].to_double(1 - get_caution());
      auto_remove_ = goal["auto_remove"].to_bool();

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

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

      id_ = goal["id"].str();
      if (leader->get_location() == dst_) {
            //goal already reached
            if (auto_remove_ && !id_.empty()) {
                  remove_goal(id_);
            } else {
                  move_ = check_move_action(leader->get_location(), leader->get_location(), !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, current_team(), *resources::units, *resources::teams, *resources::game_map);
      pathfind::plain_route route = a_star_search(leader->get_location(), dst_, 1000.0, &calc,
                  resources::game_map->w(), resources::game_map->h());
      if(route.steps.empty()) {
            LOG_AI_TESTING_AI_DEFAULT << "route empty";
            return BAD_SCORE;
      }

      const pathfind::paths leader_paths(*resources::game_map, *resources::units, leader->get_location(),
                         *resources::teams, false, false, current_team());

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

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

      if(loc.valid()) {
            move_ = check_move_action(leader->get_location(), 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"] = 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_ = *resources::units;
      const unit_map::iterator leader = units_.find_leader(get_side());

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

      // Find where the leader can move
      const pathfind::paths leader_paths(*resources::game_map, units_, leader->get_location(),
            *resources::teams, false, false, current_team());
      const map_location& keep = suitable_keep(leader->get_location(), leader_paths);

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

      // If the leader is not on keep, move him there.
      if (leader->get_location() != keep) {
            if (leader_paths.destinations.contains(keep) && units_.count(keep) == 0) {
                  move_ = check_move_action(leader->get_location(), 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.
            int current_distance = distance_between(leader->get_location(), 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->get_location(), 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 = resources::units->find_leader(get_side());
      get_villages(get_dstsrc(),get_enemy_dstsrc(),leader);
      if (moves_.size()>0) {
            return get_score();
      }
      return BAD_SCORE;
}


void get_villages_phase::execute()
{
      unit_map &units_ = *resources::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->get_location() == 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->hitpoints() / 4)
                        {
                              LOG_AI_TESTING_AI_DEFAULT << "found support target... " << new_unit->get_location() << '\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 && resources::game_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 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_ = *resources::units;
      const int ticks = SDL_GetTicks();
      best_leader_loc_ = map_location::null_location;
      if(leader != units_.end()) {
            keep_loc_ = nearest_keep(leader->get_location());
            leader_loc_ = leader->get_location();
      } 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->side() == get_side() && u_itor->movement_left()) {
                  reachmap.insert(std::make_pair(u_itor->get_location(),      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, 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::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_ = *resources::game_map;
      std::vector<team> &teams_ = *resources::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;
            }

            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 = resources::units->find(j->second);
            if (u == resources::units->end() || u->get_state("guardian")) {
                  continue;
            }

            const unit  &un = *u;
            //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_ = *resources::units;
      unit_map::iterator u_it = units_.begin();
      for(; u_it != units_.end(); ++u_it) {
            unit &u = *u_it;

            // 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->get_location());
                  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 (resources::game_map->gives_healing(dst) && (units_.find(dst) == units_.end() || dst == u_it->get_location())) {
                              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
      const unit_map& units_ = *resources::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->get_location(), leader_adj);
      }

      for(unit_map::const_iterator i = units_.begin(); i != units_.end(); ++i) {
            if (i->side() == get_side() &&
                i->movement_left() == i->total_movement() &&
                unit_map::const_iterator(i) != leader &&
                !i->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->get_location(), 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->get_location());
                        map_location best_pos, best_defensive(i->get_location());

                        double best_rating = -1000.0;
                        int best_defensive_rating = i->defense_modifier(resources::game_map->get_terrain(i->get_location()))
                              - (resources::game_map->is_village(i->get_location()) ? 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->defense_modifier(resources::game_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 - (resources::game_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->get_location(), 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;
      }

      double optimal_terrain = best_defensive_position(un->get_location(), dstsrc,
                  srcdst, enemy_dstsrc).chance_to_hit/100.0;
      const double proposed_terrain =
            un->defense_modifier(resources::game_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_ = *resources::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->get_location();
      }

      for(leader = units_.begin(); leader != units_.end(); ++leader) {
            if(leader->can_recruit() && current_team().is_enemy(leader->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) {
            int distance = distance_between(i->first, leader->get_location());
            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