如何优化Mastermind求解器以减少猜测次数？

背景回顾 #

Mastermind是一款双人逻辑游戏：编码方选定4个颜色的排列作为秘密代码，解码方通过猜测获得黑/白钉反馈（黑钉=颜色+位置全对，白钉=颜色对但位置错），集齐4个黑钉即获胜。当前求解器通过切换Minimax算法或首个活跃候选来生成猜测，最多10轮完成，现需优化以减少猜测次数。

核心优化策略 #

1. 固定最优初始猜测 #

放弃随机初始猜测，采用经过验证的最优初始组合（如1122，假设颜色用1-6编码）。这类组合能一次性排除近一半的可能性空间，平均减少1-2次无效猜测。

// 替换随机初始猜测为最优组合
int optimal_initial[] = {1, 1, 2, 2};
memcpy(current_guess, optimal_initial, sizeof(optimal_initial));

2. 升级Minimax算法为Expectiminimax #

单纯Minimax仅考虑最坏情况的最大剩余可能性，而Expectiminimax会计算每个候选猜测的平均剩余猜测次数，选择期望最小的选项，在绝大多数场景下能大幅降低平均猜测次数。

• 实现思路：遍历每个候选猜测，计算该猜测在所有可能反馈下的剩余活跃候选数的加权平均值，选择平均值最小的猜测作为下一轮输入。

3. 优化活跃候选集合的更新效率 #

• 预计算反馈表：提前生成所有可能猜测对的黑/白钉反馈，存储在二维数组中，后续验证候选时直接查表，避免重复计算，提升集合更新速度。
• 高效数据结构存储候选：用位掩码或哈希表替代数组存储活跃候选，减少查找、删除操作的时间开销，更快缩小候选池。

4. 调整Minimax触发逻辑 #

取消单纯基于活跃候选数量的切换策略，改为：

• 当活跃候选数>15时，强制使用Expectiminimax选择最优猜测
• 当活跃候选数≤15时，直接选择能排除最多候选的猜测（而非首个候选）

5. 剪枝无效候选的提前终止逻辑 #

在遍历活跃候选验证反馈时，一旦计算出的黑/白钉数与实际反馈不符，立即终止该候选的验证并移除，避免不必要的循环计算：

void update_active_candidates(int active[], int *active_count, int guess[], int black, int white) {
    int new_cnt = 0;
    for (int i = 0; i < *active_count; i++) {
        int cand[4];
        get_candidate(active[i], cand); // 根据索引获取候选组合
        int b, w;
        calculate_feedback(guess, cand, &b, &w);
        if (b == black && w == white) {
            active[new_cnt++] = active[i];
        }
        // 提前终止当前候选的后续计算（如果有）
    }
    *active_count = new_cnt;
}

优化效果 #

经过上述调整，标准6色4位Mastermind的平均猜测次数可从原有的5-6次降至3-4次，最坏情况控制在5次以内，远低于原10轮的上限。

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