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-2008 Julien Jorge
00008 
00009   This library is free software; you can redistribute it and/or
00010   modify it under the terms of the GNU Lesser General Public
00011   License as published by the Free Software Foundation; either
00012   version 2.1 of the License, or (at your option) any later version.
00013 
00014   This library is distributed in the hope that it will be useful,
00015   but WITHOUT ANY WARRANTY; without even the implied warranty of
00016   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00017   Lesser General Public License for more details.
00018 
00019   You should have received a copy of the GNU Lesser General Public
00020   License along with this library; if not, write to the Free Software
00021   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
00022 
00023   contact: julien_jorge@yahoo.fr
00024 */
00030 #include <claw/max_vector.hpp>
00031 
00032 #include <cstdlib>
00033 
00034 //**************************** gamestate **************************************
00035 
00036 /*---------------------------------------------------------------------------*/
00040 template <class Action, class Numeric>
00041 claw::ai::game::game_state<Action, Numeric>::~game_state()
00042 {
00043 
00044 } // ~game_state() [destructeur]
00045 
00046 /*---------------------------------------------------------------------------*/
00050 template <class Action, class Numeric>
00051 Numeric claw::ai::game::game_state<Action, Numeric>::min_score()
00052 {
00053   return s_min_score; 
00054 } // min_score()
00055 
00056 /*---------------------------------------------------------------------------*/
00060 template <class Action, class Numeric>
00061 Numeric claw::ai::game::game_state<Action, Numeric>::max_score()
00062 {
00063   return s_max_score; 
00064 } // max_score()
00065 
00066 /*---------------------------------------------------------------------------*/
00071 template <class Action, class Numeric>
00072 typename claw::ai::game::game_state<Action, Numeric>::score
00073 claw::ai::game::game_state<Action, Numeric>::fit
00074 ( score score_val ) const 
00075 { 
00076   if ( s_max_score < score_val ) 
00077     return s_max_score;
00078   else if ( score_val < s_min_score )
00079     return s_min_score;
00080   else
00081     return score_val;
00082 } // fit()
00083 
00084 
00085 //**************************** action_eval ************************************
00086 
00087 
00088 /*---------------------------------------------------------------------------*/
00094 template <class Action, class Numeric>
00095 claw::ai::game::action_eval<Action, Numeric>::action_eval( const Action& a,
00096                                                            const Numeric& e)
00097   : action(a), eval(e)
00098 {
00099 
00100 } // action_eval() [constructeur]
00101 
00102 /*---------------------------------------------------------------------------*/
00107 template <class Action, class Numeric>
00108 bool claw::ai::game::action_eval<Action, Numeric>::operator<
00109   ( const action_eval& ae ) const 
00110 {
00111   return eval <  ae.eval; 
00112 } // operator<()
00113 
00114 /*---------------------------------------------------------------------------*/
00119 template <class Action, class Numeric>
00120 bool claw::ai::game::action_eval<Action, Numeric>::operator==
00121   ( const action_eval& ae ) const 
00122 {
00123   return eval == ae.eval; 
00124 } // operator==()
00125 
00126 
00127 
00128 
00129 //********************************* min_max ***********************************
00130 
00131 
00132 /*---------------------------------------------------------------------------*/
00143 template <class State>
00144 typename State::score claw::ai::game::min_max<State>::operator()
00145   ( int depth, const state& current_state, bool computer_turn ) const
00146 {
00147   score score_val;
00148 
00149   // on a atteint la profondeur demandée ou la partie est terminée
00150   if ( current_state.final() || (depth == 0) )
00151     score_val = current_state.evaluate(); // on retourne l'évaluation de l'état.
00152   else
00153     {
00154       std::list<action> next_actions;
00155       typename std::list<action>::const_iterator it;
00156       state* new_state;
00157 
00158       // on récupère les états suivants.
00159       current_state.nexts_actions( next_actions );
00160 
00161       if ( next_actions.empty() )       // si on ne peut plus rien faire
00162         // on évalue l'état où l'on est.
00163         score_val = current_state.evaluate();   
00164       else
00165         {
00166           if (computer_turn)    // si c'est l'ordi qui va jouer
00167             {                                   
00168               score_val = current_state.min_score();
00169                           
00170               for (it = next_actions.begin(); it!=next_actions.end(); ++it)
00171                 {
00172                   new_state=static_cast<state*>(current_state.do_action(*it));
00173 
00174                   // on évalue le coup du joueur
00175                   score s = (*this)( depth-1, *new_state, false );
00176                                           
00177                   // on choisit l'action qui nous rapporte le plus
00178                   if (s > score_val)
00179                     score_val = s;
00180 
00181                   delete new_state;
00182                 }
00183             }
00184           else  // c'est le tour du joueur
00185             {           
00186               score_val = current_state.max_score();
00187                           
00188               for (it = next_actions.begin(); it!=next_actions.end(); ++it)
00189                 {
00190                   new_state=static_cast<state*>(current_state.do_action(*it));
00191                                   
00192                   // on évalue le coup de l'ordi
00193                   score s = (*this)( depth-1, *new_state, true );
00194                                   
00195                   // on choisit l'action qui lui rapporte le moins.
00196                   if (s < score_val)
00197                     score_val = s;
00198                                   
00199                   delete new_state;
00200                 }
00201             }
00202         }
00203     }
00204   
00205   return score_val;
00206 } // min_max::operator()
00207 
00208 
00209 
00210 
00211                 
00212 //******************************** alpha_beta *********************************
00213 
00214 
00215   /*---------------------------------------------------------------------------*/
00223 template <class State>
00224 typename State::score claw::ai::game::alpha_beta<State>::operator()
00225   ( int depth, const state& current_state, bool computer_turn ) const
00226 {
00227   return this->calcul( depth, current_state, computer_turn, 
00228                        current_state.min_score(), current_state.max_score() ) ;
00229 } // alpha_beta::operator()
00230 
00231 
00232 /*---------------------------------------------------------------------------*/
00245 template <class State>
00246 typename State::score claw::ai::game::alpha_beta<State>::calcul
00247 ( int depth, const state& current_state, bool computer_turn, score alpha,
00248   score beta ) const
00249 {
00250   score score_val;
00251                 
00252   // on a atteint la profondeur demandée ou la partie est terminée
00253   if ( current_state.final() || (depth == 0) )
00254     score_val = current_state.evaluate(); // on retourne l'évaluation de l'état.
00255   else
00256     {
00257       std::list<action> next_actions;
00258       typename std::list<action>::const_iterator it;
00259       State* new_state;
00260 
00261       // on récupère les états suivants.
00262       current_state.nexts_actions( next_actions );
00263           
00264       if ( next_actions.empty() )       // si on ne peut plus rien faire
00265         score_val = current_state.evaluate();   // on évalue l'état où l'on est.
00266       else
00267         {
00268           if (computer_turn)    // si c'est l'ordi qui va jouer
00269             {             // c'est un noeud MAX : sort l'action la plus forte
00270               score_val = current_state.min_score();
00271                           
00272               it = next_actions.begin();
00273 
00274               while ( it!=next_actions.end() && (score_val < beta) )
00275                 {
00276                   // le coup appliqué remontera le min de ses fils
00277                   new_state=static_cast<state*>(current_state.do_action(*it));
00278 
00279                   // on évalue le coup du joueur
00280                   score s = calcul( depth-1, *new_state, false, 
00281                                     std::max(alpha, score_val), beta );
00282 
00283                   // on choisit l'action qui nous rapporte le plus
00284                   if (s > score_val) 
00285                     score_val = s;
00286                                           
00287                   delete new_state;
00288                                           
00289                   ++it;
00290                 }
00291             }
00292           else    // c'est le tour du joueur
00293             {     // c'est un noeud MIN : sort l'action la plus faible
00294               score_val = current_state.max_score();
00295                                         
00296               it = next_actions.begin();
00297 
00298               while ( it!=next_actions.end() && (score_val > alpha) )
00299                 {
00300                   // le coup appliqué remontera le max de ses fils
00301                   new_state=static_cast<state*>(current_state.do_action(*it));
00302 
00303                   // on évalue le coup de l'ordi
00304                   score s = calcul( depth-1, *new_state, true, alpha,
00305                                     std::min(beta, score_val) );
00306                                                 
00307                   // on choisit l'action qui lui rapporte le moins.
00308                   if (s < score_val)
00309                     score_val = s;
00310                   ++it;
00311                                                 
00312                   delete new_state;
00313                 }
00314             }
00315         }
00316     }
00317 
00318   return score_val;
00319 } // alpha_beta::calcul()
00320 
00321 
00322 
00323 
00324 
00325 //***************************** select_action *********************************
00326 
00327 
00328 
00329 
00330 /*---------------------------------------------------------------------------*/
00340 template<class Method>
00341 void claw::ai::game::select_action<Method>::operator()
00342   ( int depth, const state& current_state, action& new_action, 
00343     bool computer_turn ) const
00344 {
00345   std::list<action> l;
00346   typename std::list<action>::iterator it;
00347   score best_eval;              
00348   Method method;
00349 
00350   // actions jouables par l'ordi
00351   current_state.nexts_actions( l );
00352   best_eval = current_state.min_score();
00353 
00354   for (it=l.begin(); it!=l.end(); ++it)
00355     {
00356       state* new_state;
00357       score eval;
00358                         
00359       // on effectue chaque action
00360       new_state = static_cast<state*>(current_state.do_action(*it));
00361       // et on regarde ce qu'elle vaut.
00362       eval = method(depth-1, *new_state, !computer_turn);
00363 
00364       delete new_state;
00365 
00366       // si c'est la meilleure, on la garde.
00367       if (eval > best_eval)
00368         {
00369           best_eval = eval;
00370           new_action = *it;
00371         }
00372     }
00373 } // select_action::operator()
00374 
00375 
00376 //*************************** select_random_action ****************************
00377 
00388 template<class Method>
00389 void claw::ai::game::select_random_action<Method>::operator()
00390   ( int depth, const state& current_state, action& new_action, 
00391     bool computer_turn ) const
00392 {
00393   std::list<action> l;
00394   typename std::list<action>::iterator it;
00395   action_eval<action, score> eval( new_action, current_state.min_score() );
00396   Method method;
00397   max_vector< action_eval<action, score> > events( eval );
00398 
00399   // actions jouables par l'ordi
00400   current_state.nexts_actions( l );
00401 
00402   for (it=l.begin(); it!=l.end(); ++it)
00403     {
00404       state* new_state;
00405                         
00406       // on effectue chaque action
00407       new_state = static_cast<state*>(current_state.do_action(*it));
00408 
00409       // et on regarde ce qu'elle vaut.
00410       eval.action = *it;
00411       eval.eval = method(depth-1, *new_state, !computer_turn);
00412 
00413       delete new_state;
00414 
00415       // si c'est la meilleure, on la garde.
00416       events.add( eval );
00417     }
00418 
00419   int i = rand() % events.get_v().size();
00420   new_action = events.get_v()[i].action;
00421 } // select_random_action::operator()
00422 

Generated on 9 Nov 2009 for CLAW Library (a C++ Library Absolutely Wonderful) by  doxygen 1.6.1