Таблица транспозиции вызывает сбой тестов (но в игре работает нормально) - PullRequest
Новая
       80

Таблица транспозиции вызывает сбой тестов (но в игре работает нормально)

0 голосов
/ 10 июля 2020

Я добавил таблицу транспонирования в свой алгоритм minmax 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++;
    }
}

Тест никогда не возвращал никаких проигрывающих состояний, пока я не добавил таблицу транспонирования, чтобы проверить, когда появляется проигрывающее состояние, я сделал тест, который проигрывает каждую перестановку проигрывающего поля, но он никогда не обнаруживал проигрывающего состояния, что могло привести к потере ИИ только в тесте 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()));
 }

1 Ответ

1 голос
/ 13 июля 2020

Я вижу, по крайней мере, два места, где могут возникать эти ошибки.

Одна потенциальная проблема находится в этой строке: 

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

Помимо проверки того, сохраняет ли таблица транспонирования результат поиск с той же глубиной, вам также необходимо проверить, что сохраненные границы в таблице совместимы с границами в таблице.

Я рассмотрел это как часть ответа на другой вопрос :

Когда вы сохраняете значения в таблице транспонирования, вам также необходимо сохранить границы альфа и бета, используемые во время поиска. Когда вы получаете значение обратно в середине поиска узла, это либо верхняя граница истинного значения (потому что значение = бета), нижняя граница истинного значения (потому что значение = альфа), либо фактическое значение узла ( альфа <значение <бета). Вам нужно сохранить это в своей таблице транспонирования. Затем, когда вы хотите повторно использовать значение, вы должны проверить, можете ли вы использовать значение с учетом ваших текущих границ альфа и бета. (Вы можете проверить это, фактически выполнив поиск после нахождения значения в таблице транспонирования, чтобы увидеть, получаете ли вы то же значение при поиске, что и в таблице.) </p>

Способ проверки этого это изменить AI::minMax. Установите флаг в значение true, если у вас есть значение, возвращаемое из таблицы транспонирования. Затем, каждый раз, когда вы возвращаете значение, если флаг таблицы транспонирования истинен, сравните значение, которое вы собираетесь вернуть, со значением, которое было найдено в таблице транспонирования. Если они не совпадают, значит, что-то не так.

Кроме того, минимакс обычно используется с играми с нулевой суммой, что означает, что сумма очков двух игроков должна быть добавлена ​​к 0. Я не знаю ' Я не знаю, что означают все возвращаемые значения в вашем коде, но иногда вы возвращаете {0, -1}, а иногда {0, -2}. Это проблема c, потому что теперь у вас есть игра с ненулевой суммой, и большая часть теории разваливается.

В частности, максимальный игрок может рассматривать {0, -1} и {0, -2} одинаково, но мин-плеер не будет. Таким образом, если порядок ходов каким-либо образом изменится, вы можете увидеть их в другом порядке, и, следовательно, значение в root дерева не будет стабильным.

В стороне, это фундаментальная проблема в многопользовательских играх. На практике это возникает, когда один игрок является королем. Они не могут сами выиграть игру, но они могут решить, кто выиграет.

...