最小-最大算法中的内存泄漏

Question

我完全是编程新手，一个月前我刚刚开始完全随机地尝试编写我自己的国际象棋引擎代码（我的目标是创造一些能打败我自己的东西。令人着迷。）所以请尽量让你的答案尽可能清楚，当我的解释不足时，请要求澄清。

目前我的引擎可以在我的 1.8Ghz 处理器上每秒分析大约 0.5 到 80 万个位置，任何关于这方面的想法也将受到欢迎，但无论如何对我来说很明显，让我的引擎更快的唯一方法是尝试以固定顺序移动，以便将错误的移动从搜索中排除。为此，我将代码从传递 int 变量更改为传递 int 指针。我的想法是只关注产生分数的动作。该代码仍然有效，但大小增加了。我用谷歌搜索并尝试了一些内存泄漏工具，但它们只告诉我泄漏内存的分配位置，我已经知道，但不知道它的地址何时丢失。

我想如果我只是 post 我的代码一些有经验的人可以马上发现泄漏。现在我已经上网寻求帮助，我发现我的代码在逻辑上等同于一个以 minimax with alpha beta pruning 的名义存在了几十年的算法。酷

int evaluate(int *board, int capture) { ... return board evaluation; }

int *Black(int *board, int depth, int *max, int *min) {
    if (depth == 0) {
        temp = malloc(20 * sizeof(int)); //eventually i will store
    }                 
    minlocal = malloc(20 * sizeof(int)); //moves next to the score
    *minlocal = *min;  //this is what i came up with so that min/max        
                       //of a higher function call doesn't get changed
    for (all moves) {
        if (depth > 0) {
            temp = whitemove(board, depth - 1, max, minlocal);
        } else {
            *temp = evaluate(board, capture);
        }
        if (*temp <= *max) {
            ;free(minlocal);
            return temp;
        }
        if (*temp < *minlocal) {
            *minlocal = *temp;
        }
        if (depth > 0) {
            free(temp);
        }
    }
    if (depth = 0) {    //<====== silly bug!
        free(temp);
    }
    return minlocal;
}

int *whitemove(int *board, int depth, int *max, int *min) {
    temp = malloc(20 * sizeof(int));
    maxlocal = malloc(20 * sizeof(int));
    *temp = -30000;
    *maxlocal = *max;
    for (all moves) {
        v = blackmove(board, depth - 1, maxlocal, min);
        if (*v > *temp) {
            free(temp);
            temp = v;
        } else {
            free(v);
        }
        if (*temp > *maxlocal) {
            *maxlocal = *temp;
        }
        if (*temp >= *min) {
            free(maxlocal);
            return temp;
        }
    }
    free(maxlocal);
    return temp;
}

看了代码你可能注意到我的东西只能打白，深度只能是偶数，这对我来说暂时无所谓。

据我所知，我采用的这种方法可能绝对是愚蠢的，但它似乎并不比以前慢，而且它应该能够存储游戏路线而不是简单的第一步。也欢迎任何关于替代方案的意见。

Answer 1

您似乎在很短的时间内掌握了良好的 C 编程技能。

但是您仍然需要改进您的风格：表示非常重要，因为它有助于避免许多愚蠢的错误并使您的代码对其他程序员和您自己都更具可读性。

还使用编译器可以通过适当的标志生成的所有警告，例如 gcc -Wall -Wextra。

Black 函数末尾有一个愚蠢的错误：

if (depth = 0)

显然应该阅读

 if (depth == 0)

这是您永远不会释放内存的地方。

可能还有其他地方您无法跟踪已分配的块，以及不需要分配的地方，如果您不需要 return 调用者使用本地数组会更快.将指向本地数组的指针作为目标数组传递也可以减少内存分配量。

Answer 2

一般来说，当您用 C 语言编写代码时，无论何时分配内存，您都需要记住您需要正确 free 它，在比较中使用双等号运算符。在我们的例子中，您有一个名为 temp 的变量，它将使用分配的内存，并且在每次为 whitemove 或 Black 初始化时，您为它分配新的内存，而不是 free调用之前分配的内存，它仍然是分配的，但你不再有它的引用。

答案在上面，下面我给大家提几点建议：

很高兴你发明了 alpha-beta 修剪而不了解它，但你需要优雅地实现它。例如，您有一个 whitemove 和一个 Black 函数。为什么把Black命名为"Black"，而不是一致命名为"blackmove"？此外，当您编写函数时，您需要尽可能通用地解决问题。白棋与黑棋有何不同？

他们试图最大化对不同方向的评价
他们可以用不同的棋子移动

现在，如果考虑到这一点，您可以将这两个函数写成一个函数。您不需要 return 大内存块，因为这不是我们打算从国际象棋引擎中知道的。您需要 return 评估和移动。您可以使用一个数组来存储最佳变化，并使用另一个数组来存储当前变化。每当您发现比以前认为最好的变体更好的变体时，就将其替换。但要避免内存泄漏 :)

最小-最大算法中的内存泄漏

Memory leak in min-max algorithm

c

memory-leaks

minimax