[SOLVED] Implementing Minimax search with Iterative Deepening

What I am doing: I am writing a chess engine in C++. I recently updated my engine's minimax search algo that uses alpha-beta pruning to utilize iterative deepening so that it can play under a time constraint. This is how it looks:


//I return a string, int pair. The string represents the best move found, while the int represents the engine evaluation for the node after said move is made

static std::pair<string, int> iterativeDeepeningSearch(Board initialPosition, int maxDepth, milliseconds maxSearchTime)
    {
        std::pair<string, int> bestMove;
        milliseconds startTime = duration_cast<milliseconds>(
            system_clock::now().time_since_epoch());

        for (int currentDepth = 1; currentDepth <= maxDepth; currentDepth++)
        {

            milliseconds currentTime = duration_cast<milliseconds>(
                system_clock::now().time_since_epoch());
            if (currentTime > startTime + maxSearchTime)
            {
                return bestMove;
            }
            std::pair<string, int> bestMoveFoundFromMinimax = minimax(initialPosition, currentDepth, INT_MIN, INT_MAX, "", "", startTime + maxSearchTime);
            if (bestMoveFoundFromMinimax.first != "") {
                bestMove = bestMoveFoundFromMinimax;
            }
        }
        return bestMove;
    }

My issue: The issue with this implementation is that, when searching at any depth larger than 1, it will search all prior depths before searching the desired depth. That is, this iterative deepening search first searches all moves at depth 1. Then, instead of picking up on depth 2 on the next search, it will search depth 1 again and then search depth 2. Then it will search depths 1 and 2 before searching depth 3. And so on.

My question: Is this the way iterative deepening is supposed to work? Each time we increment depth, we search all parent nodes as well? I imagined that each time we increment depth, it would only search all sibling nodes at the new depth. If this is, in fact, the way iterative deepening is supposed to work, how would one go about only searching the new depth rather than searching all parent nodes as well?

My minimax with iterative deepening is searching the whole tree to a given depth each time we increment the depth:

I expected minimax with iterative deepening to only search the new depth each time we increment the depth:

For reference, here is my (sloppy) minimax function utilizing alpha beta pruning:

static std::pair<string, int> minimax(Board node, int depth, int alpha, int beta, string move, string firstMove, milliseconds breakOffTime)
{
    if (breakOffTime != std::chrono::milliseconds(0))
    {
        milliseconds currentTime = duration_cast<milliseconds>(
            system_clock::now().time_since_epoch());
        if (currentTime > breakOffTime)
        {
            return std::make_pair("", 0);
        }
    }

    Moves &moves = Moves::getInstance();
    if (moves.isCheckmate(node))
    {
        if (node.getWhiteToMove())
        {
            return std::make_pair(firstMove, INT_MIN);
        }
        else
        {
            return std::make_pair(firstMove, INT_MAX);
        }
    }
    if (depth == 0)
    {
        return std::make_pair(firstMove, Rating::getCentipawnValue(node));
    }
    if (node.getWhiteToMove())
    {
        string bestMove = firstMove;
        int bestValue = INT_MIN;
        string pseudoLegalMoves = moves.pseudoLegalMovesW(node);
        if (pseudoLegalMoves.length() == 0)
        {
            return std::make_pair(firstMove, 0);
        }
        for (int i = 0; i < pseudoLegalMoves.length(); i += 4)
        {
            string individualMoveString;
            individualMoveString += pseudoLegalMoves[i];
            individualMoveString += pseudoLegalMoves[i + 1];
            individualMoveString += pseudoLegalMoves[i + 2];
            individualMoveString += pseudoLegalMoves[i + 3];
            Board tNode = moves.makeMoveAll(node, individualMoveString);
            if ((moves.unsafeForWhite(tNode) & tNode.getWK()) == 0)
            {
                std::pair<string, int> ab;
                if (firstMove == "")
                {
                    ab = minimax(tNode, depth - 1, alpha, beta, individualMoveString, individualMoveString, breakOffTime);
                }
                else
                {
                    ab = minimax(tNode, depth - 1, alpha, beta, individualMoveString, firstMove, breakOffTime);
                }
                int val = ab.second;
                string move = ab.first;
                if (val > bestValue || (val == bestValue && bestMove == ""))
                {
                    bestValue = val;
                    bestMove = move;
                }
                alpha = max(alpha, bestValue);
                if (alpha >= beta)
                {
                    break;
                }
            }
        }
        return std::make_pair(bestMove, bestValue);
    }
    else
    {
        string bestMove = firstMove;
        int bestValue = INT_MAX;
        string pseudoLegalMoves = moves.pseudoLegalMovesB(node);
        if (pseudoLegalMoves.length() == 0)
        {
            return std::make_pair(firstMove, 0);
        }
        for (int i = 0; i < pseudoLegalMoves.length(); i += 4)
        {
            string individualMoveString;
            individualMoveString += pseudoLegalMoves[i];
            individualMoveString += pseudoLegalMoves[i + 1];
            individualMoveString += pseudoLegalMoves[i + 2];
            individualMoveString += pseudoLegalMoves[i + 3];
            Board tNode = moves.makeMoveAll(node, individualMoveString);
            if ((moves.unsafeForBlack(tNode) & tNode.getBK()) == 0)
            {
                std::pair<string, int> ab;
                if (firstMove == "")
                {
                    ab = minimax(tNode, depth - 1, alpha, beta, individualMoveString, individualMoveString, breakOffTime);
                }
                else
                {
                    ab = minimax(tNode, depth - 1, alpha, beta, individualMoveString, firstMove, breakOffTime);
                }
                int val = ab.second;
                string move = ab.first;
                if (val < bestValue || (val == bestValue && bestMove == ""))
                {
                    bestValue = ab.second;
                    bestMove = ab.first;
                }
                beta = min(beta, bestValue);
                if (alpha >= beta)
                {
                    break;
                }
            }
        }
        return std::make_pair(bestMove, bestValue);
    }
}

Also, here is my full project if anybody is interested in checking it: https://github.com/ChopinDavid/Maestro-cpp

I'm not a C++ developer, so it's probably pretty sucky.