c++ - 英特尔 TBB parallel_reduce 返回不正确的结果

Question

我正在尝试使用英特尔 TBB parallel_reduce 来计算对 Connect 4 游戏中用户移动的最佳响应。我写了一个简单的函数，当传递一个列号时，它会返回一个启发式分数，该分数对应于下棋的效用。我的意图是并行调用这个函数，然后返回返回结果的减少。减少将是具有最高启发式分数的移动。

但是我发现我得到的结果不一致。我希望从并行 reduce 返回第 0 列的移动(因为我已经编写了启发式评分函数，它返回 7 - 列号作为评分)。

我附上了C++代码。这是它产生的示例输出:

Return move 0

Return move 1

Return move 2

Return move 6

Return move 4

Return move 5

Compare moves 5Return move 3 & 6

Compare moves 3 & 4

Compare moves 3 & 5

Compare moves 2 & 3

Best move is 2

我已多次查看代码，但不知所措，无法理解为什么它并不总是返回 0 作为最佳着法。它有时会返回零，但并非总是如此。正如您在上面看到的，移动 0 被评估，但归约 lambda 函数永远不会将其作为输入。任何帮助将不胜感激。我有一个模糊的怀疑，我使用的 0 的标识可能不正确。但是我不确定它应该是什么。

#include <tbb\blocked_range.h>
#include <tbb\parallel_reduce.h>

#include <iostream>
#include <vector>

int getMoveHueristicScore(int columnCounter) {

    int returnValue = 7 - columnCounter;
    return returnValue;
}

int bestHeuristicScore(int numberOfColumns) {

    std::vector<int> moveScores(numberOfColumns, -1 * INT_MAX);

    return tbb::parallel_reduce(
        tbb::blocked_range<int>(0, numberOfColumns),
        0,
        [=, &moveScores](const tbb::blocked_range<int>& range, int bestMove)->int {
        int bestScore = -1 * INT_MAX;
        for (int columnCounter = range.begin(); columnCounter != range.end(); ++columnCounter) {
            moveScores.at(columnCounter) = getMoveHueristicScore(columnCounter);
            if (moveScores.at(columnCounter) > bestScore) {
                bestScore = moveScores.at(columnCounter);
                bestMove = columnCounter;
            }
        }
        std::cout << "Return move " << bestMove << std::endl;
        return bestMove;
    },
        [=, &moveScores](int bestMove1, int bestMove2)->int {
        std::cout << "Compare moves " << bestMove1 << " & " << bestMove2 << std::endl;
        if (moveScores.at(bestMove1) > moveScores.at(bestMove2)) {
            return bestMove1;
        }
        else {
            return bestMove2;
        }
    }
    );
}

int main() {

    int bestMove = bestHeuristicScore(7);
    std::cout << "Best move is " << bestMove << std::endl;
    return 0;
}

Answer 1

在这种情况下，tbb::parallel_reduce 没有问题。问题是您的代码忽略了 func 函数的 init 参数。

TBB 对于如何执行缩减有不同的选择。它可以选择在不同的线程中为不同的子范围调用func，然后使用reduction函数组合结果；它可以在同一个线程中多次调用func，每次都传入上一次调用的结果；或者它可以结合使用这两种策略。

查看您对 func 的实现:

[=, &moveScores](const tbb::blocked_range<int>& range, int bestMove)->int {
    int bestScore = -1 * INT_MAX;
    for (int columnCounter = range.begin(); columnCounter != range.end(); ++columnCounter) {
        moveScores.at(columnCounter) = getMoveHueristicScore(columnCounter);
        if (moveScores.at(columnCounter) > bestScore) {
            bestScore = moveScores.at(columnCounter);
            bestMove = columnCounter;
        }
    }
    std::cout << "Return move " << bestMove << std::endl;
    return bestMove;
}

从未使用过init参数bestMove；相反，值 bestScore 被初始化为某个虚拟值。 TBB 可能会多次调用 func，每次都传入上一次调用计算出的 bestMove，但它会被忽略，因此最终结果将是 bestMove 来自恰好传递给最后一次调用的任何子范围。

修复方法是使用bestMove 来初始化best score，如下:

int bestScore = moveScores.at(bestMove);

然后TBB会把一次调用func的运行最好成绩带到下一次调用，确保最终结果确实是全局最好成绩。