首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >转置表导致测试失败(但在游戏中运行良好)

转置表导致测试失败(但在游戏中运行良好)
EN

Stack Overflow用户
提问于 2020-07-10 16:25:10
回答 1查看 62关注 0票数 0

我已经在我的TicTacToe最小最大算法中添加了一个转置表

代码语言:javascript
运行
复制
int AI::findBestMove()
{
    hash = tTable->recalculateHash();
    int bestMove = minMax().second;
    return bestMove;
}

std::pair<int, int> AI::minMax(int reverseDepth, std::pair<int, int> bestScoreMove, player currentPlayer, int alpha, int beta, int lastPlay)
{
    Entry e = (*tTable)[hash];
    if (e && e.depth == reverseDepth)
            return e.scoreMove;
    if (reverseDepth == 0)
        return { 0, -2 };
    else if (field->canDrawOrWin() && lastPlay != -1)
    {
        if (field->hasWon(lastPlay))
            return { evaluateScore(currentPlayer), -1 };
        else if (field->isDraw())
            return { 0, -1 };
    }
    bestScoreMove.first = currentPlayer == player::AI ? INT_MIN : INT_MAX;
    for (int i = 0; i < field->size(); i++)
    {
        if ((*field)[i] == player::None && field->isCoordWorthChecking(i))
        {
            (*field)[i] = currentPlayer;
            hash = tTable->calculateHash(hash, i);
            std::pair<int, int> scoreMove = minMax(reverseDepth - 1, bestScoreMove, getOpponent(currentPlayer), alpha, beta, i);
            if (currentPlayer == player::AI)
            {
                alpha = std::max(alpha, scoreMove.first);
                if (bestScoreMove.first < scoreMove.first)
                    bestScoreMove = { scoreMove.first, i };
            }
            else
            {
                beta = std::min(beta, scoreMove.first);
                if (bestScoreMove.first > scoreMove.first)
                    bestScoreMove = { scoreMove.first, i };
            }
            hash = tTable->calculateHash(hash, i);
            (*field)[i] = player::None;
            if (beta <= alpha)
                break;
        }
    }
    tTable->placeEntry(hash, bestScoreMove, reverseDepth);
    return bestScoreMove;
}

为了测试它,我做了一个验收测试,它运行每一个可能的棋盘,并检查人类的胜利。

代码语言:javascript
运行
复制
TEST(AcceptanceTest, EveryBoard)
{
    int winstate = 0;
    std::shared_ptr<Field> field = std::make_shared<Field>(4);
    AI ai(field);
    playEveryBoard(ai, field, winstate);
    std::cout <<"Human wins: " << winstate << std::endl;
}
void playEveryBoard(AI& ai, std::shared_ptr<Field> f, int& winstate)
{
    int bestMove = 0;
    auto it = f->begin();
    while (true)
    {
        it = std::find(it, f->end(), player::None);
        if (it == f->end())
            break;
        *it = player::Human;
        if (f->hasWon())
            winstate++;
        EXPECT_TRUE(!f->hasWon());

        bestMove = ai.findBestMove();
        if (bestMove == -1)//TIE
        {
            *it = player::None;
            break;
        }
        (*f)[bestMove] = player::AI;
        if (f->hasWon())//AI WIN
        {
            *it = player::None;
            (*f)[bestMove] = player::None;
            break;
        }

        playEveryBoard(ai, f, winstate);

        *it = player::None;
        (*f)[bestMove] = player::None;
        if (it == f->end())
            break;
        it++;
    }
}

测试从未返回任何松动状态,直到我添加了转置表,以测试松动状态出现时我进行了一个测试,播放松动字段的每个排列,但它从未发现松动状态,是什么导致AI仅在EveryBoard测试中松动?

代码语言:javascript
运行
复制
TEST(LoosePossible, AllPermutations)
{
    std::vector<int> loosingField = { 2, 3, 7, 11, 12, 13, 15 };
    do{
        std::shared_ptr<Field> field = std::make_shared<Field>(4);
        AI *ai = new AI(field);
        for (auto i : loosingField)
        {
            if ((*field)[i] != player::None || field->hasWon())
                break;
            (*field)[i] = player::Human;
            EXPECT_TRUE(!field->hasWon());
            (*field)[ai->findBestMove()] = player::AI;
        }
        delete ai;
    } while (next_permutation(loosingField.begin(), loosingField.end()));
 }
EN

回答 1

Stack Overflow用户

发布于 2020-07-13 12:40:08

我认为至少有两个地方可能会出现这些错误。

其中一个潜在的问题就是:

代码语言:javascript
运行
复制
Entry e = (*tTable)[hash];
if (e && e.depth == reverseDepth)
        return e.scoreMove;

除了检查转置表是否存储了相同深度的搜索结果外,还需要检查表中存储的边界是否与表中的边界兼容。

我在回答another question时提到了这一点。

在转置表中存储值时,还需要存储搜索期间使用的alpha和beta边界。当您在搜索过程中从节点取回一个值时,它要么是真值的上界(因为value = beta),要么是真值的下界(因为value = alpha),或者是节点的实际值(alpha < value < beta)。您需要将其存储在您的转置表中。然后,当您想要重用该值时,必须检查在给定当前alpha和beta边界的情况下是否可以使用该值。(在转置表中找到值之后,您可以通过实际执行搜索来验证这一点,以查看从搜索中获得的值是否与在表中获得的值相同。)

测试的方法是修改AI::minMax。当从转置表返回一个值时,将标志设置为true。然后,每次返回一个值时,如果转置表标志为true,则将您将要返回的值与转置表中找到的值进行比较。如果它们不是相同的,那么一定是出了问题。

此外,minimax通常用于零和游戏,这意味着两个玩家的得分总和应该加到0。我不知道所有返回值在您的代码中意味着什么,但是有时返回{0, -1},有时返回{0, -2}。这是有问题的,因为现在你有了一个非零和游戏,而且大部分理论都崩溃了。

具体地说,最大播放器可以将{0, -1}{0, -2}同等对待,但最小播放器不会。因此,如果移动顺序以任何方式更改,您可能会看到这些顺序不同,因此树根部的值将不稳定。

顺便说一句,这是多人游戏中的一个基本问题。实际上,当一个玩家是国王缔造者时,它就会出现。他们不能自己赢得比赛,但他们可以决定谁赢了。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/62830163

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档