Бесплатно исправно решавање MCTS-а у C језику у iChess.io

Здраво, Данас бих желео да вам покажем проблем са којим се суочавам већ дуго времена… Хтео сам да користим претрагу Монте Карло стабла са класичним одабиром, проширити, повратно ширење и тако даље… Проблем са којим сам се суочио је био цурење меморије, и тражио сам неко време добро решење за смањење меморије за један ниво и ефикасно ослобађање меморије. To make it correclty you have to calculate max depth and reecude from deeper to less deeper in order the tree. Rest is explain below in the code example. Thanks and Enjoy! :D.

typedef struct ch_mcts_tree {
    struct ch_mcts_tree **children;
    struct ch_mcts_tree *parent;
    float *board;
    int parents;
    int player;
    int total_count;
    int count;
    int index;
    int *visit_count;
    float *value;
    float *prob;
} ch_mcts_tree;

int ch_calculate_depth(ch_mcts_tree* node) {
    if (node == NULL) return 0;

    int max_depth = 0;
    for (int i = 0; i < node->count; ++i) {
        if (node->children[i] != NULL) {
            int child_depth = ch_calculate_depth(node->children[i]);
            if (child_depth > max_depth) {
                max_depth = child_depth;
            }
        }
    }

    return max_depth + 1;
}

ch_mcts_tree* ch_free_mcts(ch_mcts_tree* root, int exclude_index) {
    if (root == NULL) return NULL;

    int* depths = (int*)CALLOC(root->count, sizeof(int));

    for (int i = 0; i < root->count; ++i) {
        depths[i] = (i == exclude_index || root->children[i] == NULL) ? -1 : ch_calculate_depth(root->children[i]);
    }

    for (int pass = 0; pass < root->count; ++pass) {
        int max_depth = -1, max_index = -1;

        for (int i = 0; i < root->count; ++i) {
            if (depths[i] > max_depth) {
                max_depth = depths[i];
                max_index = i;
            }
        }

        if (max_index != -1 && root->children[max_index] != NULL) {
            root->children[max_index] = ch_free_mcts(root->children[max_index], -1);
            depths[max_index] = -1;
        }
    }

    FREE(depths);

    if (root->visit_count) { FREE(root->visit_count); root->visit_count = NULL; }
    if (root->value) { FREE(root->value); root->value = NULL; }
    if (root->board) { FREE(root->board); root->board = NULL; }
    if (root->prob) { FREE(root->prob); root->prob = NULL; }

    if (root->children) { FREE(root->children); root->children = NULL; }

    FREE(root);

    return NULL;
}