Negamax实现中置换表引发错误落子的问题排查

我用TypeScript开发了一款国际象棋AI，核心采用带Alpha-Beta剪枝的Negamax算法搜索可行走法。AI配置了两种启发式函数：

• 主启发式函数：用于评估Negamax树遍历中的叶节点
• 轻量启发式函数：用于对走法排序，减少搜索节点数量

为了节省计算时间，我参考维基百科Negamax页面的伪代码实现了置换表（transposition table）。虽然速度提升明显，但AI出现了错误落子的情况。我怀疑是置换表的实现导致Alpha-Beta剪枝逻辑异常，使得AI误判已剪枝的其他走法，但无法准确定位问题。

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

我已验证算法其余部分正常，仅在启用置换表时出现落子错误。尝试过的解决方法：

• 仅存储启发式分数，不保存上下界类型
• 修改正负值处理的数学逻辑
• 仅在特定深度使用置换表
• 调换置换表使用判断中的<=与>=（按逻辑应采用<=以仅使用更深搜索的分数，但两种方式均无效）

内容的提问来源于stack exchange，提问作者byte-this