Claw
1.7.3
|
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