如何在置换表中处理重复局面和棋？三人莫里斯AI优化问题

你的核心问题在于置换表设计未区分评估值的上下文类型，且重复局面的终止条件触发过早，导致本该找到的必胜路径被提前截断，错误复用了和棋结果。

具体原因 #

1. 置换表仅存原始值，无上下文信息：
   当前置换表只记录局面的评估值，但未标记该值是确切的最优结果还是临时的剪枝边界值。当某个局面在搜索早期因重复走法返回0（和棋），但后续搜索发现存在必胜路径时，置换表已缓存错误的和棋值，后续访问该局面会直接返回错误结果。

2. 重复局面终止条件优先级过高：
   isRepetition()作为优先终止条件直接返回0，会导致算法在未搜索完所有必胜走法时就提前终止并缓存和棋结果。实际上，重复走法逼和是所有走法均无法获胜时的兜底判定，而非优先终止条件。

修复方案 #

1. 改进置换表结构 #

给每个置换表条目增加上下文信息，至少包含：

• 局面哈希值
• 评估值
• 节点类型（标记值为确切结果/下界/上界）
• 搜索深度（可选，优先复用更深的搜索结果）

示例C++结构：

struct TranspositionEntry {
    uint32_t pos;
    int value;
    enum Type { EXACT, LOWER_BOUND, UPPER_BOUND } type;
    int depth;
};

std::vector<TranspositionEntry> transTable;

2. 调整终止条件与搜索逻辑 #

将重复局面判定移至所有走法搜索完成后，仅当无必胜路径时才返回和棋：

int evaluate(ThreeMensMorris &board){
    // 优先处理胜负终止条件
    if(board.isGameWon()) return -1; // 当前玩家落败，对手获胜

    uint32_t pos = board.getPosInt();
    // 置换表查询：仅复用确切结果
    for(const auto& entry : transTable){
        if(entry.pos == pos && entry.type == TranspositionEntry::EXACT){
            return entry.value;
        }
    }

    int bestValue = -100;
    bool hasLegalMoves = false;
    // 遍历所有合法走法
    for(int i = 0; i < 9; i++){
        for(int j = -1; j < 9; j++){
            if(!board.makeMove(i, j)) continue;
            hasLegalMoves = true;
            int value = -1 * evaluate(board);
            board.unmakeMove(i, j);
            if(value > bestValue) bestValue = value;
            // 剪枝：找到必胜值直接终止搜索
            if(bestValue == 1) break;
        }
        if(bestValue == 1) break;
    }

    // 所有走法搜索完成后，判断和棋
    if(!hasLegalMoves || board.isRepetition()){
        bestValue = 0;
    }

    // 存入置换表，标记为确切结果
    transTable.push_back({pos, bestValue, TranspositionEntry::EXACT, 0});
    return bestValue;
}

3. 额外优化建议 #

• 使用std::unordered_map<uint32_t, TranspositionEntry>替代数组，提升置换表查询效率。
• 结合alpha-beta剪枝进一步压缩搜索树，配合置换表可大幅提升速度。
• 确保isRepetition()实现正确：需维护历史局面序列，判断当前局面是否重复出现，避免误判。

内容的提问来源于stack exchange，提问作者RegularSalamander