Mastermind minimax algorithm

algorithm, minimax, python

Solution

1. What's wrong with your implementation

There are four mistakes.

The comment is wrong on this line:

m=max(HMList)#maximum [B,C], more left - less eliminated (min in minimax)

This is actually the "max" in the minimax (which should have been clear from the call to `max`). You are trying to find the guess that minimizes the maximum size of the groups of possible secrets that yield the same evaluation. Here we are finding the maximum size of the groups, so that's the "max".

That mistake caused you to make this one:

if m>item1Max: #max of the guesses, the max in minimax

Here you need to take the min, not the max.

On the following lines you pick the first item among `optionList` that would generate the same evaluation as `item1`:

possibleGuess=[i[:] for i in optionList if   AdjustmentInverse(maxElement)==HowManyBc(item1[:],i[:])]
nextGuess=possibleGuess[0][:]

But that's not right: the guess we want here is `item1`, not some other guess that would generate the same evaluation!

Finally, you don't properly handle the case where `optionList` has only one remaining item. In this case all possible guesses are equally good at distinguishing among this item, so the minimax procedure doesn't differentiate between the guesses. In this case you should just guess `optionList[0]`.

2. Other comments on your code

The variable names are poorly chosen. For example, what is `item1`? This is the guess that you are evaluating, so surely it should be called something like `possible_guess`? I suspect that your mistake §1.3 above was partly caused by this poor choice of variable name.

There's vast amounts of needless copying. All of your `[:]` are pointless and can be removed. The variable `List1` is also pointless (why not just assign to `optionList`?), as is `nextGuess` (which not just assign to `guess`?)

You build `dummyList` consisting of all possible secrets that would match the last guess, but then you throw away all the entries in `dummyList` that aren't also in `optionList`. So why not just loop over `optionList` and keep the entries that match? Like this:

optionList = [item for item in optionList if HowManyBc(guess, item)==BC]

You build up a table `HMList` which counts the number of occurrences of each pattern of bulls and cows. You have noted the fact that there are 14 possible (bull, cow) pairs and so you've written the functions `Adjustment` and `AdjustmentInverse` to map back and forth between (bull, cow) pairs and their indices in the list.

These functions could have much simpler implementations if you took a data-driven approach and used the built-in `list.index` method:

# Note that (3, 1) is not possible.
EVALUATIONS = [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 0), (1, 1),
               (1, 2), (1, 3), (2, 0), (2, 1), (2, 2), (3, 0), (4, 0)]

def Adjustment(evaluation):
    return EVALUATIONS.index(evaluation)

def AdjustmentInverse(index):
    return EVALUATIONS[index]

But after fixing mistake §1.3 above, you don't need `AdjustmentInverse` any more. And `Adjustment` could be avoided if you kept the counts in a `collections.Counter` instead of a list. So instead of:

HMList=[0]*14 # counts how many B/C there are for item2 in optionList
for BC1 in ListBC:
    index=Adjustment(BC1)
    HMList[index]=HMList[index]+1
m=max(HMList)

you could simply write:

m = max(Counter(ListBC).values())

3. Improved code

Evaluating a guess (your function `HowManyBc`) can be reduced to just three lines using the class `collections.Counter` from the standard library.

from collections import Counter

def evaluate(guess, secret):
    """Return the pair (bulls, cows) where `bulls` is a count of the
    characters in `guess` that appear at the same position in `secret`
    and `cows` is a count of the characters in `guess` that appear at
    a different position in `secret`.

        >>> evaluate('ABCD', 'ACAD')
        (2, 1)
        >>> evaluate('ABAB', 'AABB')
        (2, 2)
        >>> evaluate('ABCD', 'DCBA')
        (0, 4)

    """
    matches = sum((Counter(secret) & Counter(guess)).values())
    bulls = sum(c == g for c, g in zip(secret, guess))
    return bulls, matches - bulls

I happen to prefer using letters for the codes in Mastermind. `ACDB` is so much nicer to read and type than `[0, 2, 3, 1]`. But my `evaluate` function is flexible as to how you represent the codes and guesses, as long as you represent them as sequences of comparable items, so you can use lists of numbers if you prefer.

Notice also that I've written some doctests: these are a quick way to simultaneously provide examples in the documentation and to test the function.

The function `itertools.product` provides a convenient way to build the list of codes without having to write four nested loops:

from itertools import product
ALL_CODES = [''.join(c) for c in product('ABCDEF', repeat=4)]

Knuth's five-guess algorithm uses the minimax principle. So why not implement it by taking the `min` of a sequence of calls to `max`?

def knuth(secret):
    """Run Knuth's 5-guess algorithm on the given secret."""
    assert(secret in ALL_CODES)
    codes = ALL_CODES
    key = lambda g: max(Counter(evaluate(g, c) for c in codes).values())
    guess = 'AABB'
    while True:
        feedback = evaluate(guess, secret)
        print("Guess {}: feedback {}".format(guess, feedback))
        if guess == secret:
            break
        codes = [c for c in codes if evaluate(guess, c) == feedback]
        if len(codes) == 1:
            guess = codes[0]
        else:
            guess = min(ALL_CODES, key=key)

Here's an example run:

>>> knuth('FEDA')
Guess AABB: feedback (0, 1)
Guess BCDD: feedback (1, 0)
Guess AEAC: feedback (1, 1)
Guess AFCC: feedback (0, 2)
Guess FEDA: feedback (4, 0)

Problem

Original source