00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00030 #include <claw/max_vector.hpp>
00031
00032 #include <cstdlib>
00033
00034
00035
00036
00040 template <class Action, class Numeric>
00041 claw::ai::game::game_state<Action, Numeric>::~game_state()
00042 {
00043
00044 }
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 }
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 }
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 }
00083
00084
00085
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 }
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 }
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 }
00125
00126
00127
00128
00129
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
00150 if ( current_state.final() || (depth == 0) )
00151 score_val = current_state.evaluate();
00152 else
00153 {
00154 std::list<action> next_actions;
00155 typename std::list<action>::const_iterator it;
00156 state* new_state;
00157
00158
00159 current_state.nexts_actions( next_actions );
00160
00161 if ( next_actions.empty() )
00162
00163 score_val = current_state.evaluate();
00164 else
00165 {
00166 if (computer_turn)
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
00175 score s = (*this)( depth-1, *new_state, false );
00176
00177
00178 if (s > score_val)
00179 score_val = s;
00180
00181 delete new_state;
00182 }
00183 }
00184 else
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
00193 score s = (*this)( depth-1, *new_state, true );
00194
00195
00196 if (s < score_val)
00197 score_val = s;
00198
00199 delete new_state;
00200 }
00201 }
00202 }
00203 }
00204
00205 return score_val;
00206 }
00207
00208
00209
00210
00211
00212
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 }
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
00253 if ( current_state.final() || (depth == 0) )
00254 score_val = current_state.evaluate();
00255 else
00256 {
00257 std::list<action> next_actions;
00258 typename std::list<action>::const_iterator it;
00259 State* new_state;
00260
00261
00262 current_state.nexts_actions( next_actions );
00263
00264 if ( next_actions.empty() )
00265 score_val = current_state.evaluate();
00266 else
00267 {
00268 if (computer_turn)
00269 {
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
00277 new_state=static_cast<state*>(current_state.do_action(*it));
00278
00279
00280 score s = calcul( depth-1, *new_state, false,
00281 std::max(alpha, score_val), beta );
00282
00283
00284 if (s > score_val)
00285 score_val = s;
00286
00287 delete new_state;
00288
00289 ++it;
00290 }
00291 }
00292 else
00293 {
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
00301 new_state=static_cast<state*>(current_state.do_action(*it));
00302
00303
00304 score s = calcul( depth-1, *new_state, true, alpha,
00305 std::min(beta, score_val) );
00306
00307
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 }
00320
00321
00322
00323
00324
00325
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
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
00360 new_state = static_cast<state*>(current_state.do_action(*it));
00361
00362 eval = method(depth-1, *new_state, !computer_turn);
00363
00364 delete new_state;
00365
00366
00367 if (eval > best_eval)
00368 {
00369 best_eval = eval;
00370 new_action = *it;
00371 }
00372 }
00373 }
00374
00375
00376
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
00400 current_state.nexts_actions( l );
00401
00402 for (it=l.begin(); it!=l.end(); ++it)
00403 {
00404 state* new_state;
00405
00406
00407 new_state = static_cast<state*>(current_state.do_action(*it));
00408
00409
00410 eval.action = *it;
00411 eval.eval = method(depth-1, *new_state, !computer_turn);
00412
00413 delete new_state;
00414
00415
00416 events.add( eval );
00417 }
00418
00419 int i = rand() % events.get_v().size();
00420 new_action = events.get_v()[i].action;
00421 }
00422