Modello di progettazione per una IA basata su grandi alberi decisionali in C++

Question

Attualmente sto scrivendo un'IA per un gioco scritto in C++. L'intelligenza artificiale è concettualmente abbastanza semplice, attraversa solo un albero decisionale e sceglie azioni appropriate. In precedenza utilizzavo prolog per il motore decisionale, ma a causa degli altri sviluppatori che utilizzavano C++ e alcuni problemi con l'integrazione del codice prolog ora sto provando a portarlo in C++.

Attualmente ho un sacco di fatti e regole in prolog (100+). Molti esprimono le cose nella forma, se game_state quindi fa azione xyz. La maggior parte delle regole sono abbastanza semplici e alcune sono piuttosto complesse. Ho esaminato un approccio a macchina a stati finiti, ma non sembra che si adatti alle situazioni più grandi così bene. Il mio primo tentativo di codificare questo in C++ è stato un enorme incubo di se poi altre dichiarazioni di casi. Ho avuto questo tipo di codice spuntando ovunque:

if(this->current_game_state->some_condition == true){ 
     if(this->current_game_state->some_other_condition == false){  
       //some code 
     }else{ 
      return do_default_action(); 
     } 
    }else if(this->current_game->another_condition){ 
     //more code 
    } 

La complessità è diventata rapidamente ingestibile.

Se esiste un buon modo per codificare questo tipo di problema in C++? Esistono buoni schemi di progettazione per affrontare questo tipo di situazione? Non è richiesto che la logica debba essere contenuta all'interno della sorgente, deve solo essere accessibile da C++. L'unico vero requisito è che sia ragionevolmente veloce.

Ho anche guardato i motori delle regole e se abbastanza veloci potevano essere appropriati. Sai se esiste un motore di regole C++ open source che sarebbe appropriato?

Answer 1

Codice è dati e dati è codice. Hai un codice funzionante: devi solo esporlo a C++ in modo che possa essere compilato, quindi puoi implementare un interprete minimo per valutarlo.

Una possibilità è prendere le regole Prolog e tradurle nel modo più diretto possibile per una struttura dati. Forse si potrebbe progettare una semplice tabella come:

struct { 
    State coming_from; 
    Event event; 
    void (*func)(some, args); 
    State going_to; 
} rules[] = { 
    { WANDERING_AROUND, HEAR_SOUND, look_around, ENEMY_SEEN }, 
    { ENEMY_SEEN,  GUN_LOADED, fire_gun, SNEEK_AWAY }, 
    { next, rule, goes, here }, 
    etc... 
} 

Allo stesso modo, le chiamate di funzione possono compilare strutture di dati in modo tale che sembra simile al vostro originale Prolog:

void init_rules() { 
    rule("Parent", "Bill", "John"); 
    rule("Parent", "Paul", "Bill"); 
    // 99 more rules go here... 
} 

Poi si implementare un semplice interprete attraversare quella struttura dati e trovare le risposte che ti servono. Con meno di 1000 regole, un approccio alla forza bruta alla ricerca è probabile che sia abbastanza veloce, ma puoi sempre diventare furbo in seguito e provare a fare le cose come farebbe un vero ambiente Prolog quando sarà il momento.

Answer 2

Non capisco perché una macchina a stati finiti non sia sufficiente per il tuo gioco. È un modo comune per fare ciò che vuoi. Potresti renderlo guidato dai dati per mantenerti pulito da azioni concrete. Lo stato finito m. è anche descritto in "AI per Game Dev" O'Reilly (David M. Bourg & Glenn Seemann) Forse vuoi dividere le tue regole in diverse serie di regole più piccole per mantenere la macchina piccola e comprensibile.

Answer 3

Se si desidera convertire il vostro codice di prologo al codice C++, uno sguardo alla biblioteca Castor (C++) che consentono Logic Programming in C++: http://www.mpprogramming.com/Cpp/Default.aspx

non l'ho provato io stesso modo, Non so nulla delle sue prestazioni.

Se si desidera utilizzare uno stato macchina, dare un'occhiata a Boost.Meta State Machine

Answer 4

Come circa l'uso di mercurio?è fondamentalmente costruito per interfacciarsi con il codice C.

Answer 5

È possibile utilizzare il polimorfismo. Chiamare una funzione virtuale è effettivamente un grosso interruttore/caso che è fatto e ottimizzato per te dal compilatore.

class GameState { 
    virtual void do_something() { std::cout << "GameState!"; } 
    // some functions 
    virtual ~GameState() {} 
}; 
class SomeOtherState : public GameState { 
    // some other functions 
    virtual void do_something() { std::cout << "SomeOtherState!"; } 
}; 
class MyFinalState : public GameState { 
    virtual void do_something() { std::cout << "MyOtherState!"; } 
}; 
class StateMachine { 
    std::auto_ptr<GameState> curr_state; 
public: 
    StateMachine() 
     : curr_state(NULL) {} 
    void DoSomething() { curr_state->DoSomething(); } 
    void SetState(GameState* ptr) { curr_state = ptr; } 
    template<typename T> void SetState() { curr_state = new T; } 
}; 
int main() { 
    StateMachine sm; 
    sm.SetState(new SomeOtherState()); 
    sm.SetState<SomeOtherState>(); 
    sm.DoSomething(); // prints "SomeOtherState!" 
    sm.SetState<MyFinalState>(); 
    sm.DoSomething(); // prints "MyFinalState!" 
} 

Nell'esempio di cui sopra, non ho bisogno di passare su uno qualsiasi degli stati, o anche sapere che esistono diversi stati o quello che fanno (nella classe StateMachine, comunque), la logica di selezione è stata fatta dal compilatore.

Answer 6

Cercare di eguagliare la potenza espressiva di Prolog con le macchine a stati è come cercare di superare una macchina con una bicicletta.

Castor è probabilmente la strada da percorrere. È molto leggero e consente un'interpolazione uniforme tra la programmazione logica e il resto del C++. Dai un'occhiata ai video tutorial su http://www.mpprogramming.com/cpp