Как уменьшить возможности в Mastermind на основе обратной связи?

Question

Я следую алгоритму Дональда Кнута, чтобы решить игру Mastermind.

Однако, я застрял на два шага:

1. Создать набор S оставшихся возможностей (на данный момент есть 1296). Первое предположение - абаб.

2. Удалите все возможности от S, чтобы не дал такой же результат цветных и белых колышек, если бы они были .

3. Для каждого возможного предположения (не обязательно в S) вычислить , сколько возможностей из S будет устранено для каждого возможного цветной/белый балл. Оценка догадки является наименьшей из таких значений . Играйте с догадкой с наивысшим счетом (минимакс).

4. Вернитесь на шаг 2, пока не получите его правильно.

сгенерировать множество возможностей (в основном 6 х 6 х 6 х 6). Отсюда я сформулирую начальное предположение aabb. «Управляющий» дает обратную связь в виде x белые штифты и y черные колышки.

Белые штифты указывают, что один из четырех цветов в нашей догадке был правильным, но в неправильном месте. Черные привязки показывают, что один из четырех цветов в нашей догадке был правильным и в правильном месте.

Отсюда следующее предположение должно быть изменено на основе этой информации.

Мой вопрос: учитывая, что моя первая догадка aabb, и мой отзыв есть, скажем 1w1b, какие перестановки я могу удалить из множества возможностей?

Answer 1

def CalcScore(answer, solution): 
    """ A function that will return a tupple of the number of white & black pegs """ 
    ... 

todel = [] 
for poss in poss_answers: # Assuming that poss_answers is a list/array of possible ansers 
    if not current_score == CalcScore(ThisTry, poss): 
     todel.append(poss) 
for delthis in todel: 
    poss_answers.remove(delthis) 

Answer 2

На втором этапе это совершенно ясно. Ниже приведена объясненная версия.

Вы можете перебрать любую подстановоку, вычислив ее оценку (например, 3w, 1w3b и т. Д.) В отношении текущей догадки и удалите те перестановки, которые дают разный балл, соответствующий фактическому счету.