c++中基于AI的大型决策树设计模式

Question

我目前正在为一款用c++编写的游戏编写人工智能。人工智能在概念上相当简单，它只需遍历决策树并选择适当的操作。我以前使用prolog作为决策引擎，但由于其他开发人员使用c++，以及集成prolog代码时出现一些问题，我现在尝试将其移植到c++。

目前，我在prolog (100+)中有一堆事实和规则。很多东西都是以这样的形式表达出来的，如果是game_state，那么就执行action xyz。大多数规则都相当简单，但也有少数规则相当复杂。我研究了有限状态机方法，但它似乎不能很好地扩展到更大的情况。我第一次尝试用c++编写这段代码时，使用if then else case语句是一场巨大的噩梦。我发现到处都是这样的代码：

    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
    }

复杂性很快就变得难以控制。

有没有一种很好的方法来在c++中编码这类问题？有没有什么好的设计模式来处理这种情况？并不要求逻辑必须包含在源代码中，只需要可以从c++访问它。唯一真正的要求是它相当快。

我还研究了规则引擎，如果速度足够快，它们可能是合适的。您是否知道是否有合适的开源c++规则引擎？

Answer 1

代码就是数据，数据就是代码。你已经有了可以工作的代码-你只需要将它以一种它可以编译的方式公开给C++，然后你就可以实现一个最小的解释器来评估它。

一种可能性是采用Prolog规则，并以最直接的方式将它们转换为数据结构。也许你可以设计一个简单的表格，如下所示：

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

类似地，函数调用可以填充数据结构，使其看起来与原始Prolog相似：

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

然后实现一个简单的解释器来遍历该数据结构并找到所需的答案。在少于1000条规则的情况下，暴力搜索方法可能足够快，但你可以在以后变得聪明起来，并在时机成熟时尝试以真正的Prolog环境的方式来做事情。

Answer 2

您可以使用多态性。调用一个虚函数实际上是一个大的开关/案例，编译器已经为你完成并优化了它。

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

在上面的示例中，我不需要切换任何状态，甚至不需要知道不同状态的存在或它们的作用(无论如何，在StateMachine类中)，选择逻辑是由编译器完成的。

Answer 3

如果您想要将prolog代码转换为c++代码，请看一下Castor库(C++)，它支持在C++中进行逻辑编程：http://www.mpprogramming.com/Cpp/Default.aspx

我自己还没有试过，所以我对它的性能一无所知。

如果您想使用状态机，请看一下Boost.Meta状态机