Transposition Table is causing tests to fail(but runs fine in game)

Question

I have added a transposition table to my TicTacToe minmax algorithm

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;
}

To test it I made an acceptance test that plays every possible board and checks for human wins

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++;
    }
}

The test never returned any loosing states until I added the transposition table, to test when the loosing state appears I made a test that plays every permutation of the loosing field, but it never found a loosing state, what could cause the AI to loose only in the EveryBoard test?

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()));
 }

Answer 1

I see at least two places these errors could be arising.

One potential problem is in this line:

Entry e = (*tTable)[hash];
if (e && e.depth == reverseDepth)
        return e.scoreMove;

In addition to checking if the transposition table stores the result of a search that is the same depth, you also need to check that the stored bounds in the table are compatible with the bounds in the table.

I addressed this as part of an answer to another question:

When you store values in the transposition table, you also need to store the alpha and beta bounds used during the search. When you get a value back at a node mid-search it is either an upper bound on the true value (because value = beta), a lower bound on the true value (because value = alpha) or the actual value of the node (alpha < value < beta). You need to store this in your transposition table. Then, when you want to re-use the value, you have to check that you can use the value given your current alpha and beta bounds. (You can validate this by actually doing the search after finding the value in the transposition table to see if you get the same value from search that you got in the table.)

The way to test this is to modify AI::minMax. Set a flag to true when you have a value returned from the transposition table. Then, each time you return a value, if the transposition table flag is true, compare the value you are about to return to the value that was found in the transposition table. If they are not the same, then something is wrong.

In addition, minimax is typically used with zero-sum games, which means that the sum of scores for the two players should add to 0. I don't know what all the returned values mean in your code, but sometimes you are returning {0, -1} and sometimes {0, -2}. This is problematic, because now you have a non-zero-sum game and much of the theory falls apart.

In particular, the max player may treat {0, -1} and {0, -2} the same, but the min player will not. Thus, if the move ordering changes in any way you may see these in different orders, and thus the value at the root of the tree will not be stable.

As an aside, this is a fundamental issue in multi-player games. Practically speaking it arises when one player is a king-maker. They can't win the game themselves, but they can decide who does.