What is wrong with my transition table in my negamax implementation?

Question

I'm writing a Chess AI in TypeScript which uses negamax with alpha beta pruning to search through possible moves. It uses two heuristics: 1) the main heuristic, which evaluates leaf nodes in the negamax tree traversal, and 2) a simple inexpensive heuristic that is used to order moves for the tree traversal in the hopes of eliminating nodes from the search.

I've attempted to implement a transposition table to save computation time. I've made the attempt a few times, the last of which I've taken from pseudocode on the Wikipedia page on negamax. It is saving a lot of time, but it's also making bad moves. I suspect there is an issue with the alpha beta pruning when using my implementation, thus it's returning bad moves thinking that we've pruned the rest of the moves already. However, I'm not able to identify exactly where the problem is. I've pasted the code of the algorithm below. I've tried doing modifications to the math regarding the negative and positive to ensure those are in order, but they don't seem to make a difference. I've also tried storing just the value, nothing with lower bounds or upper bounds, but that also seems to make erroneous moves (though in a different way):

/**
 * Depth first search: negamax with a/b pruning
 */
private lookAheadAtMove(
    boardState: ChessBoardState,
    player: ChessPlayer,
    enemy: ChessPlayer,
    depthRemaining: number,
    alphaPrune: number,
    betaPrune: number,
    negateMult: number,
    //pathMoves: ChessBoardSingleMove[],
    transpositionTable: Map<string, iTranspositionTableEntry>
): iLookahedResponse {
    let bestMoveH: iChessAiHeuristicEvaluation = {
        score: -Infinity,
        data: {},
    };
    //let bestMovePath = pathMoves;
    let bestMove!: ChessBoardSingleMove;

    const transpositionTableKey = boardState.toString();

    if (depthRemaining === 0) {
        // base case, depth is 0
        bestMoveH = this.heuristic.getScore(boardState);
        bestMoveH.score *= negateMult;
    } else {
        // default, keep looking
        const possibleMoves: {
            move: ChessBoardSingleMove;
            score: number;
        }[] = [];
        // sort based on initial board state analysis
        for (const move of boardState
            .getPossibleMovesForPlayer(player)
            .getMoves()) {
            const moveIsGood = this.tryMakeMove(boardState, move);
            if (moveIsGood) {
                const score =
                    this.sortHeuristic.getScore(boardState).score *
                    negateMult;

                possibleMoves.push({
                    move,
                    score,
                });
                boardState.undoLastMove();
            }
        }

        // sort the moves based on initial heuristic estimate
        possibleMoves.sort((a, b) => b.score - a.score);

        let alphaOriginal = alphaPrune;

        for (const { move } of possibleMoves) {
            let thisMoveH!: iLookahedResponse;
            if (transpositionTable.has(transpositionTableKey)) {
                const tableResult = transpositionTable.get(transpositionTableKey)!;
                if (tableResult.depthRemaining <= depthRemaining) {
                    switch (tableResult.type) {
                        case 'exact':
                            thisMoveH = {...tableResult};
                            thisMoveH.hScore.score *= negateMult;
                            break;
                        case 'upperbound':
                            alphaPrune = Math.max(alphaPrune, tableResult.hScore.score * negateMult);
                            break;
                        case 'lowerbound':
                            betaPrune = Math.min(betaPrune, tableResult.hScore.score * negateMult);
                            break;
                    }
                }
            }

            // if we didn't grab from the transposition table, make the move now
            if (!thisMoveH) {
                boardState.setPiecesFromMove(move, "");
                thisMoveH = this.lookAheadAtMove(
                    boardState,
                    enemy,
                    player,
                    depthRemaining - 1,
                    -betaPrune,
                    -alphaPrune,
                    -negateMult,
                    transpositionTable
                );
                // cleanup for next iteration
                boardState.undoLastMove();
                thisMoveH.hScore.score *= -1;
            }


            // compare scores
            if (thisMoveH.hScore.score >= bestMoveH.score) {
                bestMoveH = thisMoveH.hScore;
            }

            // add to transposition table
            let type: 'exact' | 'lowerbound' | 'upperbound';
            if (bestMoveH.score <= alphaOriginal) {
                type = 'upperbound';
            } else if (bestMoveH.score >= betaPrune) {
                type = 'lowerbound';
            } else {
                type = 'exact';
            }
            // multiply back by negate multi to put the score to to absolute value
            const tableScore = { ...thisMoveH.hScore };
            tableScore.score *= negateMult;
            transpositionTable.set(transpositionTableKey, {
                depthRemaining,
                move,
                hScore: tableScore,
                type
            });

            if (bestMoveH.score > alphaPrune) {
                alphaPrune = bestMoveH.score;
                bestMove = move;

            }


            if (alphaPrune >= betaPrune) {
                break;
            }
        }
    }

    const returnValue = { hScore: bestMoveH, move: bestMove };

    return returnValue;
}

I verified the rest of the algorithm works as expected, so the problems I'm seeing with move selection only occur when the transition table is in place. I've tried resolving this by:

• Storing only the heuristic score instead of those upperbound/lowerbound types
• Modifying the math to handle the negation in different ways.
• Only using the table at certain depths.
• Swapping "<=" with ">=" on the line which checks whether to use the transposition table or not (it should be <= so we only use a score if it was taken deeper in the tree, as I understand it, but I tried both).

Answer 1

If your code works fine without transposition tables then there is nothing wrong with your alpha/beta. Alpha/beta always gives the same result as normal mini-/negamax, it is just an enhancement to not look at unnecessary moves.

A good source to look into is the Chessprogramming site. I also like this YouTube series which goes through the concepts on a nice level.

Transposition Tables are very hard to debug unfortunately. Have you verified that your hash is calculated correctly?