C++递归构建游戏树深度失控问题及低内存优化咨询

使用State类表示游戏状态，目标是遍历所有可能的游戏状态并构建游戏树（存储为Node类的vector，示例未给出Node类）。要求构建树过程中尽可能降低内存占用，仅让持续增加的Node占用内存，而非遍历过程中的状态。

当前代码 #

#include <iostream>
#include <vector>

class State {
    public:
        State step(int action) {
          State new_state(*this);
          return new_state;
        };
        
        std::vector<int> legal_actions() {
            std::vector<int> v = {7, 5, 1};
            return v;
        }
};

void build_tree(State &state, int depth = 0) {
    if (depth == 2) {
        return;
    }
    std::vector<int> actions = state.legal_actions();
    for (auto action : actions) {
        std::cout << "action: " << action << " depth: " << depth << std::endl;
        State new_state = state.step(action);
        build_tree(state, ++depth);
    }  
}

int main() {
    State state;

    build_tree(state);

    return 0;
}

当前代码问题 #

遍历不会在深度1处停止，实际输出陷入无限递归：

action: 7 depth: 0
action: 7 depth: 1
action: 5 depth: 2
action: 7 depth: 3
action: 7 depth: 4
action: 7 depth: 5
action: 7 depth: 6
action: 7 depth: 7
action: 7 depth: 8
action: 7 depth: 9
... and so on

期望的游戏树结构与输出 #

期望构建两层游戏树（根节点深度0，子节点深度1），每个深度0节点对应3个深度1子节点，对应输出如下：

action: 7 depth: 0
action: 7 depth: 1
action: 5 depth: 1
action: 1 depth: 1
action: 5 depth: 0
action: 7 depth: 1
action: 5 depth: 1
action: 1 depth: 1
action: 1 depth: 0
action: 7 depth: 1
action: 5 depth: 1
action: 1 depth: 1

代码修复方案 #

当前代码的核心问题有两个：

1. 递归调用时传递原state而非新生成的new_state，导致状态未正确推进
2. 使用++depth修改循环内的深度变量，导致后续循环的深度被错误累加

修复后的build_tree函数：

void build_tree(State &state, int depth = 0) {
    if (depth == 2) {
        return;
    }
    std::vector<int> actions = state.legal_actions();
    for (auto action : actions) {
        std::cout << "action: " << action << " depth: " << depth << std::endl;
        State new_state = state.step(action);
        // 传递新状态，使用depth+1而非修改原depth变量
        build_tree(new_state, depth + 1);
    }  
}

修复说明：

• 递归时传入new_state，确保每个子节点基于当前状态的后续状态遍历
• 使用depth + 1作为下一层深度，避免破坏循环内的深度变量，保证兄弟节点的深度计算正确

低内存构建游戏树的优化建议 #

1. 避免状态冗余复制 #

将State的step函数改为原地修改，或提供复制方法按需保留原状态，减少临时对象的内存占用：

class State {
public:
    // 原地修改状态
    void step(int action) {
        // 执行状态修改逻辑（例如修改内部成员变量）
    }
    
    // 按需复制状态
    State copy() const {
        return State(*this);
    }
    
    std::vector<int> legal_actions() {
        return {7, 5, 1};
    }
};

使用时可通过复制+原地修改的方式遍历：

void build_tree(State state, int depth = 0) {
    if (depth == 2) {
        return;
    }
    std::vector<int> actions = state.legal_actions();
    for (auto action : actions) {
        std::cout << "action: " << action << " depth: " << depth << std::endl;
        State child_state = state.copy();
        child_state.step(action);
        build_tree(child_state, depth + 1);
    }
}

2. 用迭代遍历替代递归 #

递归会占用栈内存，深度较大时易栈溢出；迭代式遍历更易控制内存：

struct NodeInfo {
    State state;
    int depth;
};

void build_tree_iterative(State root_state) {
    std::vector<NodeInfo> stack;
    stack.push_back({root_state, 0});
    
    while (!stack.empty()) {
        auto current = stack.back();
        stack.pop_back();
        
        if (current.depth == 2) {
            continue;
        }
        
        std::vector<int> actions = current.state.legal_actions();
        // 反向遍历保证输出顺序与递归一致
        for (auto it = actions.rbegin(); it != actions.rend(); ++it) {
            int action = *it;
            std::cout << "action: " << action << " depth: " << current.depth << std::endl;
            State new_state = current.state;
            new_state.step(action);
            stack.push_back({new_state, current.depth + 1});
        }
    }
}

3. 仅存储必要的节点数据 #

游戏树的Node类无需存储完整State，只需存储从父节点到当前节点的动作和父节点索引，需要时再推导状态：

struct Node {
    int action;          // 父节点到当前节点的动作
    int parent_index;    // 父节点在vector中的索引
};

std::vector<Node> game_tree;

void build_tree_with_minimal_nodes(State state, int parent_idx, int depth = 0) {
    if (depth == 2) {
        return;
    }
    std::vector<int> actions = state.legal_actions();
    for (auto action : actions) {
        game_tree.push_back({action, parent_idx});
        std::cout << "action: " << action << " depth: " << depth << std::endl;
        State new_state = state.step(action);
        build_tree_with_minimal_nodes(new_state, game_tree.size() - 1, depth + 1);
    }
}

需要恢复状态时，从根节点开始沿父索引遍历动作序列即可重建，大幅减少内存占用。

4. 使用内存池复用对象 #

对于频繁创建销毁的State对象，用内存池预先分配一批对象，遍历过程中复用，避免频繁内存分配释放的开销。

内容的提问来源于stack exchange，提问作者Paolo