Python实现MasterMind破解器时Knuth方法的应用故障排查

问题描述 #

我正在用Python开发桌游MasterMind的代码破解器，规则与算法参考MasterMind桌游标准规则。目前卡在破解器的第6步——应用Knuth的minimax技术选择下一个猜测：该技术需选择“最差响应得分最小”的猜测，响应得分指已知反馈后集合S中剩余的可能密码数，猜测得分为所有响应得分的最大值（最坏情况），且优先从S中选最优猜测。

我的问题是：实现该步骤的代码无法正确生成最优组合，经常返回不在集合S中的结果。例如当秘密密码为(4,5,5,4)时，剩余3种可能组合，但代码返回176个“最优组合”且均不在其中；部分游戏从首次猜测开始就无S内的最优组合，导致破解无效。

问题代码 #

def choose_next_guess(remaining_combinations, set_S):
    conn = sqlite3.connect('SolverMM.sqlite3')
    cur = conn.cursor()
    cur.executescript(
        """DROP TABLE IF EXISTS solver;
        CREATE TABLE solver(ID INTEGER PRIMARY KEY AUTOINCREMENT, combination TEXT, maximum INTEGER);""")
    # All possible feedbacks
    feedbacks = [(4, 0, 0), (3, 0, 1), (2, 2, 0), (2, 1, 1), (2, 0, 2), (1, 3, 0), (1, 2, 1), (1, 0, 3), 
        (1, 0, 3),(0, 4, 0), (0, 3, 1), (0, 2, 2), (0, 0, 4), (0, 0, 4)]

    for combination in remaining_combinations:
        max_remaining = 0
        for feedback in feedbacks:
            # evaluation method returns quantity of remaining possible combinations (returns an integer)
            set_S = evaluate(feedback, combination)
            # Storing worst-case-scenario (the remaining combinations that a feedback provided with a guess)
            if set_S > max_remaining:
                max_remaining = set_S
        cur.execute("INSERT INTO solver (combination, maximum) VALUES (?, ?);", (','.join(map(str, combination)),   max_remaining))

    conn.commit()
    cur.execute("SELECT combination FROM solver WHERE maximum = (SELECT MIN(maximum) FROM solver);")
    best_combination = cur.fetchall()
    best_combination_copy = best_combination.copy()
    return best_combination

核心错误排查 #

1. 反馈列表存在重复元素 #

feedbacks列表里重复出现(1, 0, 3)和(0, 0, 4)，虽然不影响max值计算，但属于冗余，且可能掩盖反馈类型是否完整的问题，需先去重。

2. evaluate函数调用逻辑完全颠倒 #

Knuth算法的核心逻辑是：对于每个候选猜测，计算该猜测对集合S中所有可能密码生成的反馈，统计每个反馈对应的S子集大小，取这些大小的最大值作为该猜测的minimax得分。而你的代码是固定反馈和猜测去查询数量，完全违背了算法逻辑。

3. 未优先选择集合S内的最优猜测 #

当前代码仅从remaining_combinations中筛选猜测，且未在得分相同的候选中优先保留属于S的组合，不符合Knuth算法“优先选S内最优解”的要求。

4. 数据库操作冗余低效 #

每次函数调用都创建数据库表属于不必要的开销，直接用字典存储得分即可大幅提升效率。

修复后的代码示例 #

def calculate_feedback(guess, secret):
    """计算猜测与秘密密码的反馈：(完全匹配数, 颜色匹配位置不匹配数, 不匹配数)"""
    guess_copy = list(guess)
    secret_copy = list(secret)
    exact = 0
    # 统计完全匹配
    for i in range(len(guess_copy)):
        if guess_copy[i] == secret_copy[i]:
            exact += 1
            guess_copy[i] = None
            secret_copy[i] = None
    # 统计颜色匹配但位置不匹配
    color_match = 0
    for g in guess_copy:
        if g is not None and g in secret_copy:
            color_match += 1
            secret_copy.remove(g)
    no_match = len(guess) - exact - color_match
    return (exact, color_match, no_match)

def choose_next_guess(set_S, all_possible_combinations):
    score_dict = {}
    
    # 遍历所有候选猜测（Knuth算法允许使用全部可能组合，不限于S）
    for guess in all_possible_combinations:
        feedback_counts = {}
        # 统计该猜测对S中每个密码的反馈分布
        for secret in set_S:
            fb = calculate_feedback(guess, secret)
            feedback_counts[fb] = feedback_counts.get(fb, 0) + 1
        # 取最坏情况的子集大小作为该猜测的得分
        max_count = max(feedback_counts.values()) if feedback_counts else 0
        score_dict[guess] = max_count
    
    # 筛选出得分最小的所有候选
    min_max_score = min(score_dict.values())
    best_candidates = [g for g, score in score_dict.items() if score == min_max_score]
    
    # 优先返回属于S的最优候选
    s_candidates = [g for g in best_candidates if g in set_S]
    return s_candidates if s_candidates else best_candidates

额外说明 #

• all_possible_combinations需包含MasterMind所有可能的密码组合（比如4位6色的场景下是6^4=1296种）
• set_S是当前剩余的可能密码集合，每次根据反馈更新后传入
• 需确保set_S使用集合类型或可快速判断元素是否存在的结构，提升筛选效率

内容的提问来源于stack exchange，提问作者André Buro