Claw 1.7.0
game_ai.tpp
Go to the documentation of this file.
00001 /*
00002   CLAW - a C++ Library Absolutely Wonderful
00003 
00004   CLAW is a free library without any particular aim but being useful to 
00005   anyone.
00006 
00007   Copyright (C) 2005 Sébastien Angibaud
00008   Copyright (C) 2005-2011 Julien Jorge
00009 
00010   This library is free software; you can redistribute it and/or
00011   modify it under the terms of the GNU Lesser General Public
00012   License as published by the Free Software Foundation; either
00013   version 2.1 of the License, or (at your option) any later version.
00014 
00015   This library is distributed in the hope that it will be useful,
00016   but WITHOUT ANY WARRANTY; without even the implied warranty of
00017   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00018   Lesser General Public License for more details.
00019 
00020   You should have received a copy of the GNU Lesser General Public
00021   License along with this library; if not, write to the Free Software
00022   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
00023 
00024   contact: julien.jorge@gamned.org
00025 */
00031 #include <claw/max_vector.hpp>
00032 
00033 #include <cstdlib>
00034 
00035 //**************************** gamestate **************************************
00036 
00037 /*---------------------------------------------------------------------------*/
00041 template<typename Action, typename Numeric>
00042 claw::ai::game::game_state<Action, Numeric>::~game_state()
00043 {
00044   // nothing to do
00045 } // game_state::~game_state()
00046 
00047 /*---------------------------------------------------------------------------*/
00051 template <typename Action, typename Numeric>
00052 typename claw::ai::game::game_state<Action, Numeric>::score
00053 claw::ai::game::game_state<Action, Numeric>::min_score()
00054 {
00055   return s_min_score; 
00056 } // game_state::min_score()
00057 
00058 /*---------------------------------------------------------------------------*/
00062 template <typename Action, typename Numeric>
00063 typename claw::ai::game::game_state<Action, Numeric>::score
00064 claw::ai::game::game_state<Action, Numeric>::max_score()
00065 {
00066   return s_max_score; 
00067 } // game_state::max_score()
00068 
00069 /*---------------------------------------------------------------------------*/
00074 template<typename Action, typename Numeric>
00075 typename claw::ai::game::game_state<Action, Numeric>::score
00076 claw::ai::game::game_state<Action, Numeric>::fit
00077 ( score score_val ) const 
00078 { 
00079   if ( s_max_score < score_val ) 
00080     return s_max_score;
00081   else if ( score_val < s_min_score )
00082     return s_min_score;
00083   else
00084     return score_val;
00085 } // game_state::fit()
00086 
00087 
00088 //**************************** action_eval ************************************
00089 
00090 
00091 /*---------------------------------------------------------------------------*/
00097 template <typename Action, typename Numeric>
00098 claw::ai::game::action_eval<Action, Numeric>::action_eval
00099 ( const Action& a, const Numeric& e)
00100   : action(a), eval(e)
00101 {
00102 
00103 } // action_eval::action_eval()
00104 
00105 /*---------------------------------------------------------------------------*/
00110 template <typename Action, typename Numeric>
00111 bool claw::ai::game::action_eval<Action, Numeric>::operator<
00112   ( const action_eval& ae ) const 
00113 {
00114   return eval <  ae.eval; 
00115 } // action_eval::operator<()
00116 
00117 #if 0
00118 /*---------------------------------------------------------------------------*/
00123 template <typename Action, typename Numeric>
00124 bool claw::ai::game::action_eval<Action, Numeric>::operator==
00125   ( const action_eval& ae ) const 
00126 {
00127   return eval == ae.eval; 
00128 } // action_eval::operator==()
00129 #endif
00130 
00131 
00132 
00133 //********************************* min_max ***********************************
00134 
00135 
00136 /*---------------------------------------------------------------------------*/
00143 template<typename State>
00144 typename claw::ai::game::min_max<State>::score
00145 claw::ai::game::min_max<State>::operator()
00146   ( int depth, const state& current_state, bool computer_turn ) const
00147 {
00148   score score_val;
00149 
00150   // we reached a final state or we are not allowed to search more.
00151   if ( current_state.final() || (depth == 0) )
00152     score_val = current_state.evaluate();
00153   else
00154     {
00155       std::list<action> next_actions;
00156       typename std::list<action>::const_iterator it;
00157       state* new_state;
00158 
00159       // get all reachable states
00160       current_state.next_actions( next_actions );
00161 
00162       if ( next_actions.empty() )
00163         score_val = current_state.evaluate();   
00164       else if (computer_turn)
00165   {                                   
00166     score_val = current_state.min_score();
00167                           
00168     for (it = next_actions.begin(); it!=next_actions.end(); ++it)
00169       {
00170         new_state=static_cast<state*>(current_state.do_action(*it));
00171 
00172         // evaluate the action of the human player
00173         score s = (*this)( depth-1, *new_state, false );
00174                                           
00175         // and keep the best action he can do.
00176         if (s > score_val)
00177     score_val = s;
00178 
00179         delete new_state;
00180             }
00181   }
00182       else  // human player's turn
00183   {           
00184     score_val = current_state.max_score();
00185 
00186     for (it = next_actions.begin(); it!=next_actions.end(); ++it)
00187       {
00188         new_state=static_cast<state*>(current_state.do_action(*it));
00189                                   
00190         // evaluate the action of the computer player
00191         score s = (*this)( depth-1, *new_state, true );
00192                                   
00193         // and keep the worst action he can do
00194         if (s < score_val)
00195     score_val = s;
00196       
00197         delete new_state;
00198             }
00199         }
00200     }
00201   
00202   return score_val;
00203 } // min_max::operator()
00204 
00205 
00206 
00207 
00208                 
00209 //******************************** alpha_beta *********************************
00210 
00211 
00212 /*---------------------------------------------------------------------------*/
00219 template <typename State>
00220 typename State::score claw::ai::game::alpha_beta<State>::operator()
00221   ( int depth, const state& current_state, bool computer_turn ) const
00222 {
00223   return this->compute
00224     ( depth, current_state, computer_turn, current_state.min_score(),
00225       current_state.max_score() );
00226 } // alpha_beta::operator()
00227 
00228 /*---------------------------------------------------------------------------*/
00237 template<typename State>
00238 typename claw::ai::game::alpha_beta<State>::score
00239 claw::ai::game::alpha_beta<State>::compute
00240 ( int depth, const state& current_state, bool computer_turn, score alpha,
00241   score beta ) const
00242 {
00243   score score_val;
00244                 
00245   // we reached a final state or we are not allowed to search more.
00246   if ( current_state.final() || (depth == 0) )
00247     score_val = current_state.evaluate();
00248   else
00249     {
00250       std::list<action> next_actions;
00251       typename std::list<action>::const_iterator it;
00252       State* new_state;
00253 
00254       // get all reachable states
00255       current_state.next_actions( next_actions );
00256           
00257       if ( next_actions.empty() )
00258         score_val = current_state.evaluate();
00259       else if (computer_turn)
00260   {
00261     score_val = current_state.min_score();
00262                           
00263     it = next_actions.begin();
00264 
00265     while ( it!=next_actions.end() && (score_val < beta) )
00266       {
00267         new_state=static_cast<state*>(current_state.do_action(*it));
00268 
00269         // evaluate the action of the human player
00270         score s = compute
00271     ( depth-1, *new_state, false, std::max(alpha, score_val), beta );
00272 
00273         // and keep the best action he can do.
00274         if (s > score_val) 
00275     score_val = s;
00276                                           
00277         delete new_state;
00278                                           
00279         ++it;
00280       }
00281   }
00282       else // human player's turn
00283   {
00284     score_val = current_state.max_score();
00285                                         
00286     it = next_actions.begin();
00287 
00288     while ( it!=next_actions.end() && (score_val > alpha) )
00289       {
00290         new_state=static_cast<state*>(current_state.do_action(*it));
00291 
00292         // evaluate the action of the computer player
00293         score s = compute
00294     ( depth-1, *new_state, true, alpha, std::min(beta, score_val) );
00295                                                 
00296         // and keep the worst action he can do
00297         if (s < score_val)
00298     score_val = s;
00299         ++it;
00300                                                 
00301         delete new_state;
00302             }
00303         }
00304     }
00305 
00306   return score_val;
00307 } // alpha_beta::compute()
00308 
00309 
00310 
00311 
00312 
00313 //***************************** select_action *********************************
00314 
00315 
00316 
00317 
00318 /*---------------------------------------------------------------------------*/
00326 template<typename Method>
00327 void claw::ai::game::select_action<Method>::operator()
00328   ( int depth, const state& current_state, action& new_action, 
00329     bool computer_turn ) const
00330 {
00331   std::list<action> l;
00332   typename std::list<action>::iterator it;
00333   score best_eval;              
00334   Method method;
00335 
00336   // get all reachable states
00337   current_state.next_actions( l );
00338   best_eval = current_state.min_score();
00339 
00340   for (it=l.begin(); it!=l.end(); ++it)
00341     {
00342       state* new_state;
00343       score eval;
00344                         
00345       // try and evaluate each action
00346       new_state = static_cast<state*>(current_state.do_action(*it));
00347       eval = method(depth-1, *new_state, !computer_turn);
00348 
00349       delete new_state;
00350 
00351       // we keep one of the best actions
00352       if (eval > best_eval)
00353         {
00354           best_eval = eval;
00355           new_action = *it;
00356         }
00357     }
00358 } // select_action::operator()
00359 
00360 
00361 //*************************** select_random_action ****************************
00362 
00370 template<typename Method>
00371 void claw::ai::game::select_random_action<Method>::operator()
00372   ( int depth, const state& current_state, action& new_action, 
00373     bool computer_turn ) const
00374 {
00375   std::list<action> l;
00376   typename std::list<action>::iterator it;
00377   action_eval<action, score> eval( new_action, current_state.min_score() );
00378   Method method;
00379   max_vector< action_eval<action, score> > events( eval );
00380 
00381   // get all reachable states
00382   current_state.next_actions( l );
00383 
00384   for (it=l.begin(); it!=l.end(); ++it)
00385     {
00386       state* new_state;
00387                         
00388       // try and evaluate each action
00389       new_state = static_cast<state*>(current_state.do_action(*it));
00390 
00391       eval.action = *it;
00392       eval.eval = method(depth-1, *new_state, !computer_turn);
00393 
00394       delete new_state;
00395 
00396       // keep the best actions.
00397       events.add( eval );
00398     }
00399 
00400   std::size_t i = (double)rand()/(RAND_MAX + 1) * events.get_v().size();
00401   new_action = events.get_v()[i].action;
00402 } // select_random_action::operator()
00403