libclaw-dev 1.7.0-2 / usr / include / claw / impl / game_ai.tpp

/*
  CLAW - a C++ Library Absolutely Wonderful

  CLAW is a free library without any particular aim but being useful to 
  anyone.

  Copyright (C) 2005 Sébastien Angibaud
  Copyright (C) 2005-2011 Julien Jorge

  This library is free software; you can redistribute it and/or
  modify it under the terms of the GNU Lesser General Public
  License as published by the Free Software Foundation; either
  version 2.1 of the License, or (at your option) any later version.

  This library is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  Lesser General Public License for more details.

  You should have received a copy of the GNU Lesser General Public
  License along with this library; if not, write to the Free Software
  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

  contact: julien.jorge@gamned.org
*/
/**
 * \file game_ai.tpp
 * \brief Implémentation de fonctions d'intelligence artificielle.
 * \author Julien Jorge & Sébastien Angibaud
 */
#include <claw/max_vector.hpp>

#include <cstdlib>

//**************************** gamestate **************************************

/*---------------------------------------------------------------------------*/
/**
 * \brief Destructor.
 */
template<typename Action, typename Numeric>
claw::ai::game::game_state<Action, Numeric>::~game_state()
{
  // nothing to do
} // game_state::~game_state()

/*---------------------------------------------------------------------------*/
/**
 * \brief Get the minimal score a state can get.
 */
template <typename Action, typename Numeric>
typename claw::ai::game::game_state<Action, Numeric>::score
claw::ai::game::game_state<Action, Numeric>::min_score()
{
  return s_min_score; 
} // game_state::min_score()

/*---------------------------------------------------------------------------*/
/** 
 * \brief Get the maximal score a state can get.
 */
template <typename Action, typename Numeric>
typename claw::ai::game::game_state<Action, Numeric>::score
claw::ai::game::game_state<Action, Numeric>::max_score()
{
  return s_max_score; 
} // game_state::max_score()

/*---------------------------------------------------------------------------*/
/** 
 * \brief Truncate a score to fit in the range (min_score(), max_score()).
 * \param score_val The value to fit.
 */
template<typename Action, typename Numeric>
typename claw::ai::game::game_state<Action, Numeric>::score
claw::ai::game::game_state<Action, Numeric>::fit
( score score_val ) const 
{ 
  if ( s_max_score < score_val ) 
    return s_max_score;
  else if ( score_val < s_min_score )
    return s_min_score;
  else
    return score_val;
} // game_state::fit()


//**************************** action_eval ************************************


/*---------------------------------------------------------------------------*/
/**
 * \brief Constructor.
 * \param a The evaluated action.
 * \param e The evaluation of the action.
 */
template <typename Action, typename Numeric>
claw::ai::game::action_eval<Action, Numeric>::action_eval
( const Action& a, const Numeric& e)
  : action(a), eval(e)
{

} // action_eval::action_eval()

/*---------------------------------------------------------------------------*/
/**
 * \brief Compare with an otreh action.
 * \param ae The other action.
 */
template <typename Action, typename Numeric>
bool claw::ai::game::action_eval<Action, Numeric>::operator<
  ( const action_eval& ae ) const 
{
  return eval <  ae.eval; 
} // action_eval::operator<()

#if 0
/*---------------------------------------------------------------------------*/
/**
 * \brief Egalité de deux actions.
 * \return vrai si this->eval == ae.eval.
 */
template <typename Action, typename Numeric>
bool claw::ai::game::action_eval<Action, Numeric>::operator==
  ( const action_eval& ae ) const 
{
  return eval == ae.eval; 
} // action_eval::operator==()
#endif



//********************************* min_max ***********************************


/*---------------------------------------------------------------------------*/
/**
 * \brief Apply the min-max algorithm to find the best action.
 * \param depth Depth of the search subtree we are allowed to explore.
 * \param current_state The state of the game.
 * \param computer_turn Tell if the next action is done by the computer.
 */
template<typename State>
typename claw::ai::game::min_max<State>::score
claw::ai::game::min_max<State>::operator()
  ( int depth, const state& current_state, bool computer_turn ) const
{
  score score_val;

  // we reached a final state or we are not allowed to search more.
  if ( current_state.final() || (depth == 0) )
    score_val = current_state.evaluate();
  else
    {
      std::list<action> next_actions;
      typename std::list<action>::const_iterator it;
      state* new_state;

      // get all reachable states
      current_state.next_actions( next_actions );

      if ( next_actions.empty() )
        score_val = current_state.evaluate();   
      else if (computer_turn)
	{                                   
	  score_val = current_state.min_score();
                          
	  for (it = next_actions.begin(); it!=next_actions.end(); ++it)
	    {
	      new_state=static_cast<state*>(current_state.do_action(*it));

	      // evaluate the action of the human player
	      score s = (*this)( depth-1, *new_state, false );
                                          
	      // and keep the best action he can do.
	      if (s > score_val)
		score_val = s;

	      delete new_state;
            }
	}
      else  // human player's turn
	{           
	  score_val = current_state.max_score();

	  for (it = next_actions.begin(); it!=next_actions.end(); ++it)
	    {
	      new_state=static_cast<state*>(current_state.do_action(*it));
                                  
	      // evaluate the action of the computer player
	      score s = (*this)( depth-1, *new_state, true );
                                  
	      // and keep the worst action he can do
	      if (s < score_val)
		score_val = s;
		  
	      delete new_state;
            }
        }
    }
  
  return score_val;
} // min_max::operator()




                
//******************************** alpha_beta *********************************


/*---------------------------------------------------------------------------*/
/**
 * \brief Apply the alpha-beta algorithm to find the best action.
 * \param depth Depth of the search subtree we are allowed to explore.
 * \param current_state The state of the game.
 * \param computer_turn Tell if the next action is done by the computer.
 */
template <typename State>
typename State::score claw::ai::game::alpha_beta<State>::operator()
  ( int depth, const state& current_state, bool computer_turn ) const
{
  return this->compute
    ( depth, current_state, computer_turn, current_state.min_score(),
      current_state.max_score() );
} // alpha_beta::operator()

/*---------------------------------------------------------------------------*/
/**
 * \brief Find the best action using an alpha-beta algorithm.
 * \param depth Depth of the search subtree we are allowed to explore.
 * \param current_state The state of the game.
 * \param computer_turn Tell if the next action is done by the computer.
 * \param alpha Worst score of the current player.
 * \param beta Best score of the other player.
 */
template<typename State>
typename claw::ai::game::alpha_beta<State>::score
claw::ai::game::alpha_beta<State>::compute
( int depth, const state& current_state, bool computer_turn, score alpha,
  score beta ) const
{
  score score_val;
                
  // we reached a final state or we are not allowed to search more.
  if ( current_state.final() || (depth == 0) )
    score_val = current_state.evaluate();
  else
    {
      std::list<action> next_actions;
      typename std::list<action>::const_iterator it;
      State* new_state;

      // get all reachable states
      current_state.next_actions( next_actions );
          
      if ( next_actions.empty() )
        score_val = current_state.evaluate();
      else if (computer_turn)
	{
	  score_val = current_state.min_score();
                          
	  it = next_actions.begin();

	  while ( it!=next_actions.end() && (score_val < beta) )
	    {
	      new_state=static_cast<state*>(current_state.do_action(*it));

	      // evaluate the action of the human player
	      score s = compute
		( depth-1, *new_state, false, std::max(alpha, score_val), beta );

	      // and keep the best action he can do.
	      if (s > score_val) 
		score_val = s;
                                          
	      delete new_state;
                                          
	      ++it;
	    }
	}
      else // human player's turn
	{
	  score_val = current_state.max_score();
                                        
	  it = next_actions.begin();

	  while ( it!=next_actions.end() && (score_val > alpha) )
	    {
	      new_state=static_cast<state*>(current_state.do_action(*it));

	      // evaluate the action of the computer player
	      score s = compute
		( depth-1, *new_state, true, alpha, std::min(beta, score_val) );
                                                
	      // and keep the worst action he can do
	      if (s < score_val)
		score_val = s;
	      ++it;
                                                
	      delete new_state;
            }
        }
    }

  return score_val;
} // alpha_beta::compute()





//***************************** select_action *********************************




/*---------------------------------------------------------------------------*/
/**
 * \brief Select an action using the given method.
 * \param depth Maximum depth of the search tree.
 * \param current_state The state of the game.
 * \param new_action (in/out) Best known action.
 * \param computer_turn Tell if the action is done by the computer.
 */
template<typename Method>
void claw::ai::game::select_action<Method>::operator()
  ( int depth, const state& current_state, action& new_action, 
    bool computer_turn ) const
{
  std::list<action> l;
  typename std::list<action>::iterator it;
  score best_eval;              
  Method method;

  // get all reachable states
  current_state.next_actions( l );
  best_eval = current_state.min_score();

  for (it=l.begin(); it!=l.end(); ++it)
    {
      state* new_state;
      score eval;
                        
      // try and evaluate each action
      new_state = static_cast<state*>(current_state.do_action(*it));
      eval = method(depth-1, *new_state, !computer_turn);

      delete new_state;

      // we keep one of the best actions
      if (eval > best_eval)
        {
          best_eval = eval;
          new_action = *it;
        }
    }
} // select_action::operator()


//*************************** select_random_action ****************************

/**
 * \brief Select a random action among the best ones.
 * \param depth Maximum depth of the search tree.
 * \param current_state The state of the game.
 * \param new_action (in/out) Best known action.
 * \param computer_turn Tell if the action is done by the computer.
 */    
template<typename Method>
void claw::ai::game::select_random_action<Method>::operator()
  ( int depth, const state& current_state, action& new_action, 
    bool computer_turn ) const
{
  std::list<action> l;
  typename std::list<action>::iterator it;
  action_eval<action, score> eval( new_action, current_state.min_score() );
  Method method;
  max_vector< action_eval<action, score> > events( eval );

  // get all reachable states
  current_state.next_actions( l );

  for (it=l.begin(); it!=l.end(); ++it)
    {
      state* new_state;
                        
      // try and evaluate each action
      new_state = static_cast<state*>(current_state.do_action(*it));

      eval.action = *it;
      eval.eval = method(depth-1, *new_state, !computer_turn);

      delete new_state;

      // keep the best actions.
      events.add( eval );
    }

  std::size_t i = (double)rand()/(RAND_MAX + 1) * events.get_v().size();
  new_action = events.get_v()[i].action;
} // select_random_action::operator()