claw::ai::game::alpha_beta< State > Class Template Reference

Sélection d'une action avec la méthode Alpha Beta. More...

#include <game_ai.hpp>

List of all members.

Public Types

typedef State state
typedef State::action action
typedef State::score score

Public Member Functions

score operator() (int depth, const state &current_state, bool computer_turn) const
 Evaluation d'un coup par la méthode alpha_beta avec élagage alpha béta.

Private Member Functions

score calcul (int depth, const state &current_state, bool computer_turn, score alpha, score beta) const
 Evaluation d'un coup par la méthode alpha_beta.

Detailed Description

template<class State>
class claw::ai::game::alpha_beta< State >

Sélection d'une action avec la méthode Alpha Beta.

Author:
Julien Jorge & Sébastien Angibaud

Definition at line 134 of file game_ai.hpp.


Member Typedef Documentation

template<class State >
typedef State::action claw::ai::game::alpha_beta< State >::action

Definition at line 138 of file game_ai.hpp.

template<class State >
typedef State::score claw::ai::game::alpha_beta< State >::score

Definition at line 139 of file game_ai.hpp.

template<class State >
typedef State claw::ai::game::alpha_beta< State >::state

Definition at line 137 of file game_ai.hpp.


Member Function Documentation

template<class State >
State::score claw::ai::game::alpha_beta< State >::calcul ( int  depth,
const state current_state,
bool  computer_turn,
score  alpha,
score  beta 
) const [inline, private]

Evaluation d'un coup par la méthode alpha_beta.

Todo:
Voir si un coup est gagnant, les suivants du même niveau ne sont pas testés.
Parameters:
depth profondeur.
current_state état du jeu.
computer_turn indique si c'est au tour de l'ordinateur.
alpha Borne inférieure.
beta Borne supérieure.

Definition at line 247 of file game_ai.tpp.

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()

template<class State >
State::score claw::ai::game::alpha_beta< State >::operator() ( int  depth,
const state current_state,
bool  computer_turn 
) const [inline]

Evaluation d'un coup par la méthode alpha_beta avec élagage alpha béta.

Parameters:
depth profondeur.
current_state état du jeu.
computer_turn indique si c'est au tour de l'ordinateur .

Definition at line 225 of file game_ai.tpp.

00226 {
00227   return this->calcul( depth, current_state, computer_turn, 
00228                        current_state.min_score(), current_state.max_score() ) ;
00229 } // alpha_beta::operator()


The documentation for this class was generated from the following files:

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