0

我正在尝试实现 Donald Knuth 的算法来解决 Mastermind，详情如下：http: //en.wikipedia.org/wiki/Mastermind_(board_game)#Five-guess_algorithm

我的大部分代码都在工作，但我无法让 Minimax 步骤工作（在类的get_guess方法中ComputerGuesser）。我已经看过Mastermind minimax algorithm但我不知道我做错了什么。

帮助将不胜感激，谢谢。

反馈类

class Feedback(object):
    def __init__(self, number_in_correct_place, number_in_incorrect_place):
        self.number_in_correct_place = number_in_correct_place
        self.number_in_incorrect_place = number_in_incorrect_place

    def __str__(self):
        return (self.number_in_correct_place, self.number_in_incorrect_place).__str__()

    def __eq__(self, other):
        return self.number_in_correct_place == other.number_in_correct_place and self.number_in_incorrect_place == other.number_in_incorrect_place

    def __hash__(self):
        prime1 = 31
        prime2 = 17
        return (prime1 * self.number_in_correct_place) + (prime2 * self.number_in_incorrect_place)

实用方法

def generate_all_possibilities(code_length, number_of_colours):
    return [p for p in itertools.product(range(1, number_of_colours + 1), repeat=code_length)]


def get_feedback(code, guess):
    assert len(guess) == len(code)

    number_in_correct_place = 0
    number_in_incorrect_place = 0
    matched = [False] * len(code)
    for i in range(len(code)):
        if guess[i] == code[i]:
            number_in_correct_place += 1
            matched[i] = True

    for i in range(len(code)):
        if guess[i] != code[i] and guess[i] in code:
            for j in range(len(code)):
                if guess[i] == code[j] and not matched[j]:
                    number_in_incorrect_place += 1
                    matched[j] = True
                    break

    return Feedback(number_in_correct_place, number_in_incorrect_place)


def filter_possibilities(possibilities, feedback, guess):
    return [p for p in possibilities if feedback == get_feedback(guess, p)]

电脑猜谜

from collections import Counter
from guesser import Guesser
from utils import generate_all_possibilities, filter_possibilities, get_feedback


class ComputerGuesser(Guesser):
    def __init__(self, code_length, number_of_colours):
        super(ComputerGuesser, self).__init__(code_length, number_of_colours)
        self.all_possibilities = generate_all_possibilities(code_length, number_of_colours)
        self.filtered_possibilities = generate_all_possibilities(code_length, number_of_colours)

    def alert_feedback(self, feedback, guess):
        self.filtered_possibilities = filter_possibilities(self.filtered_possibilities, feedback, guess)

    def get_guess(self):
        key = lambda g: max(Counter(get_feedback(g, c) for c in self.filtered_possibilities).values())
        guess = min(self.all_possibilities, key=key)
        return guess

编辑：运行代码（添加了一些打印语句）会产生以下结果：

Code: [3, 1, 4, 3]
12 turns remaining
Guess: (1, 1, 2, 2) Feedback: (1, 0)
Number of possibilities left: 256
11 turns remaining
Guess: (1, 3, 4, 4) Feedback: (1, 2)
Number of possibilities left: 21
10 turns remaining
Guess: (3, 1, 4, 5) Feedback: (3, 0)
Number of possibilities left: 3
9 turns remaining
Guess: (1, 1, 1, 3) Feedback: (2, 0)
Number of possibilities left: 1
8 turns remaining
Guess: (1, 1, 1, 1) Feedback: (1, 0)
Number of possibilities left: 1
7 turns remaining
Guess: (1, 1, 1, 1) Feedback: (1, 0)
Number of possibilities left: 1
6 turns remaining
Guess: (1, 1, 1, 1) Feedback: (1, 0)
Number of possibilities left: 1
5 turns remaining
Guess: (1, 1, 1, 1) Feedback: (1, 0)
Number of possibilities left: 1
4 turns remaining
Guess: (1, 1, 1, 1) Feedback: (1, 0)
Number of possibilities left: 1
3 turns remaining
Guess: (1, 1, 1, 1) Feedback: (1, 0)
Number of possibilities left: 1
2 turns remaining
Guess: (1, 1, 1, 1) Feedback: (1, 0)
Number of possibilities left: 1
1 turns remaining
Guess: (1, 1, 1, 1) Feedback: (1, 0)
Number of possibilities left: 1
4

0 回答 0