game_ai.tpp

Go to the documentation of this file.

/*
  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
*/
#include <claw/max_vector.hpp>

#include <cstdlib>

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

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

/*---------------------------------------------------------------------------*/
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()

/*---------------------------------------------------------------------------*/
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()

/*---------------------------------------------------------------------------*/
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 ************************************


/*---------------------------------------------------------------------------*/
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()

/*---------------------------------------------------------------------------*/
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
/*---------------------------------------------------------------------------*/
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 ***********************************


/*---------------------------------------------------------------------------*/
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 *********************************


/*---------------------------------------------------------------------------*/
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()

/*---------------------------------------------------------------------------*/
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 *********************************




/*---------------------------------------------------------------------------*/
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 ****************************

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()