Patrón de diseño para gran árbol de decisión basado en IA en C++

Question

Actualmente estoy escribiendo una IA para un juego que está escrito en C++. La IA es conceptualmente bastante simple, simplemente se ejecuta a través de un árbol de decisión y selecciona las acciones apropiadas. Anteriormente estaba usando Prolog para el motor de decisión, pero debido a que los otros desarrolladores usan C++ y algunos problemas con la integración del código de prólogo, ahora intento portarlo a C++.

Actualmente tengo un montón de hechos y reglas en prolog (más de 100). Muchos expresan cosas en la forma, si game_state entonces realiza la acción xyz. La mayoría de las reglas son bastante simples, y algunas son bastante complejas. Miré un enfoque de máquina de estados finitos, pero eso no parecía escalar tan bien a las situaciones más grandes. Mi primer intento de codificar esto en C++ fue una gran pesadilla de si las otras declaraciones de caso. Tuve este tipo de código apareciendo en todas partes:

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 complejidad se hizo rápidamente inmanejable.

¿Hay una buena manera de codificar este tipo de problema en C++? ¿Hay algún patrón de diseño bueno para tratar este tipo de situación? No es necesario que la lógica deba estar contenida dentro de la fuente, solo debe ser accesible desde C++. El único requisito real es que sea razonablemente rápido.

También miré los motores de reglas y si eran lo suficientemente rápidos podrían ser apropiados. ¿Sabes si hay un motor de reglas C++ de código abierto que sería apropiado?

Answer 1

El código es Datos y los datos son Código. Tienes código de trabajo, solo tienes que exponerlo a C++ de una manera que pueda compilar, luego puedes implementar un intérprete mínimo para evaluarlo.

Una posibilidad es tomar las reglas de Prolog y traducirlas de la manera más directa posible a una estructura de datos. Tal vez usted podría diseñar una tabla sencilla como:

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... 
} 

Del mismo modo, las llamadas a funciones pueden poblar las estructuras de datos de tal manera que sea similar a su Prolog originales:

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

A continuación, implementar un intérprete sencilla atravesar esa estructura de datos y encontrar las respuestas que necesita. Con menos de 1000 reglas, es probable que un enfoque de fuerza bruta en la búsqueda sea lo suficientemente rápido, pero siempre puedes ser inteligente más adelante e intentar hacer las cosas de la manera que lo haría un entorno de Prolog real cuando llegue el momento.

Answer 2

Realmente no entiendo por qué una máquina de estados finitos no es suficiente para su juego. Es una forma común de hacer lo que quieras. Podrías convertirlo en información impulsada para mantener tu código limpio de acciones concretas. El estado finito m. también se describe en "AI para Game Dev" O'Reilly (David M. Bourg & Glenn Seemann) Es posible que desee dividir las reglas en varios conjuntos de reglas más pequeñas para mantener la máquina pequeña y comprensible.

Answer 3

Si desea convertir su código de prólogo a código C++, echar un vistazo a la biblioteca de ricino (C++) que permiten la programación lógica en C++: http://www.mpprogramming.com/Cpp/Default.aspx

no he probado yo mismo modo, No sé nada sobre su rendimiento.

Si desea utilizar una máquina de estados, echar un vistazo a Boost.Meta Máquina de Estados

Answer 4

¿Qué tal el uso de mercurio?básicamente está construido para interactuar con el código C.

Answer 5

Puede usar polimorfismo. Llamar a una función virtual es efectivamente un interruptor/caja grande que está hecho y optimizado para usted por el compilador.

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!" 
} 

En el ejemplo anterior, no tenía necesidad de cambiar sobre cualquiera de los estados, o incluso saber que existen diferentes estados o lo que hacen (en la clase StateMachine, de todos modos), la lógica de selección que se hizo por el compilador

Answer 6

Intentar hacer coincidir el poder expresivo de Prolog con las máquinas de estado es como intentar correr más rápido que un automóvil con una bicicleta.

Castor es probablemente el camino a seguir. Es muy liviano y permite una interoperabilidad fluida entre la programación lógica y el resto de C++. Echa un vistazo a los videos tutoriales en http://www.mpprogramming.com/cpp