我已经在我的TicTacToe最小最大算法中添加了一个转置表
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;
}
为了测试它,我做了一个验收测试,它运行每一个可能的棋盘,并检查人类的胜利。
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测试中松动?
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()));
}
发布于 2020-07-13 12:40:08
我认为至少有两个地方可能会出现这些错误。
其中一个潜在的问题就是:
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}
同等对待,但最小播放器不会。因此,如果移动顺序以任何方式更改,您可能会看到这些顺序不同,因此树根部的值将不稳定。
顺便说一句,这是多人游戏中的一个基本问题。实际上,当一个玩家是国王缔造者时,它就会出现。他们不能自己赢得比赛,但他们可以决定谁赢了。
https://stackoverflow.com/questions/62830163
复制相似问题