00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00031 #include <claw/max_vector.hpp>
00032
00033 #include <cstdlib>
00034
00035
00036
00037
00041 template<typename Action, typename Numeric>
00042 claw::ai::game::game_state<Action, Numeric>::~game_state()
00043 {
00044
00045 }
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 }
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 }
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 }
00086
00087
00088
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 }
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 }
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 }
00129 #endif
00130
00131
00132
00133
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
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
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
00173 score s = (*this)( depth-1, *new_state, false );
00174
00175
00176 if (s > score_val)
00177 score_val = s;
00178
00179 delete new_state;
00180 }
00181 }
00182 else
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
00191 score s = (*this)( depth-1, *new_state, true );
00192
00193
00194 if (s < score_val)
00195 score_val = s;
00196
00197 delete new_state;
00198 }
00199 }
00200 }
00201
00202 return score_val;
00203 }
00204
00205
00206
00207
00208
00209
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 }
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
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
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
00270 score s = compute
00271 ( depth-1, *new_state, false, std::max(alpha, score_val), beta );
00272
00273
00274 if (s > score_val)
00275 score_val = s;
00276
00277 delete new_state;
00278
00279 ++it;
00280 }
00281 }
00282 else
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
00293 score s = compute
00294 ( depth-1, *new_state, true, alpha, std::min(beta, score_val) );
00295
00296
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 }
00308
00309
00310
00311
00312
00313
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
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
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
00352 if (eval > best_eval)
00353 {
00354 best_eval = eval;
00355 new_action = *it;
00356 }
00357 }
00358 }
00359
00360
00361
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
00382 current_state.next_actions( l );
00383
00384 for (it=l.begin(); it!=l.end(); ++it)
00385 {
00386 state* new_state;
00387
00388
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
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 }
00403