Mastermind minimax algorithm
Question: I am trying to implement in python Donald Knuth's algorithm for codebreaking
mastermind in not more than 5 moves. I have checked my code several times, and
it seems to follow the algorithm, as its stated here:
<http://en.wikipedia.org/wiki/Mastermind_(board_game)#Five-guess_algorithm>

However, I get that some of the secrets take 7 or even 8 moves to accomplish.
Here is the code:

    
    
    #returns how many bulls and cows there are
    def HowManyBc(guess,secret):
        invalid=max(guess)+1
        bulls=0
        cows=0
        r=0
        while r<4:
            if guess[r]==secret[r]:
                bulls=bulls+1
                secret[r]=invalid
                guess[r]=invalid
            r=r+1
        r=0
        while r<4:
            p=0
            while p<4:
                if guess[r]==secret[p] and guess[r]!=invalid:
                    cows=cows+1
                    secret[p]=invalid
                    break
                p=p+1
            r=r+1    
        return [bulls,cows]
    
    # sends every BC to its index in HMList
    def Adjustment(BC1):
        if BC1==[0,0]:
            return 0
        elif BC1==[0,1]:
            return 1
        elif BC1==[0,2]:
            return 2
        elif BC1==[0,3]:
           return 3
        elif BC1==[0,4]:
            return 4
        elif BC1==[1,0]:
            return 5
        elif BC1==[1,1]:
            return 6
        elif BC1==[1,2]:
            return 7
        elif BC1==[1,3]:
            return 8
        elif BC1==[2,0]:
            return 9
        elif BC1==[2,1]:
            return 10
        elif BC1==[2,2]:
            return 11
        elif BC1==[3,0]:
            return 12
        elif BC1==[4,0]:
        return 13
    # sends every index in HMList to its BC
    def AdjustmentInverse(place):
        if place==0:
            return [0,0]
        elif place==1:
            return [0,1]
        elif place==2:
            return [0,2]
        elif place==3:
            return [0,3]
        elif place==4:
            return [0,4]
        elif place==5:
            return [1,0]
        elif place==6:
            return [1,1]
        elif place==7:
            return [1,2]
        elif place==8:
            return [1,3]
        elif place==9:
            return [2,0]
        elif place==10:
            return [2,1]
        elif place==11:
            return [2,2]
        elif place==12:
            return [3,0]
        elif place==13:
            return [4,0]   
    # gives minimum of positive list without including its zeros    
    def MinimumNozeros(List1):
        minimum=max(List1)+1
        for item in List1:
            if item!=0 and item<minimum:
                minimum=item
        return minimum
    
    #list with all possible guesses
    allList=[]
    for i0 in range(0,6):
        for i1 in range(0,6):
            for i2 in range(0,6):
                for i3 in range(0,6):
                    allList.append([i0,i1,i2,i3])
    TempList=[[0,0,5,4]]
    for secret in TempList:
        guess=[0,0,1,1]
        BC=HowManyBc(guess[:],secret[:])
        counter=1
        optionList=[]
        for i0 in range(0,6):
            for i1 in range(0,6):
                for i2 in range(0,6):
                    for i3 in range(0,6):
                        optionList.append([i0,i1,i2,i3])
        while BC!=[4,0]:
            dummyList=[] #list with possible secrets for this guess
            for i0 in range(0,6):
                for i1 in range(0,6):
                    for i2 in range(0,6):
                        for i3 in range(0,6):
                            opSecret=[i0,i1,i2,i3]
                            if HowManyBc(guess[:],opSecret[:])==BC:
                                dummyList.append(opSecret)
            List1=[item for item in optionList if item in dummyList]
            optionList=List1[:] # intersection of optionList and dummyList
            item1Max=0
            for item1 in allList:
                ListBC=[] # [list of all [bulls,cows] in optionList
                for item2 in optionList:
                    ListBC.append(HowManyBc(item1[:],item2[:]))
                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)#maximum [B,C], more left - less eliminated (min in minimax)
                maxList=[i for i, j in enumerate(HMList) if j == m]
                maxElement=maxList[0] #index with max
                possibleGuess=[]
                if m>item1Max: #max of the guesses, the max in minimax
                    item1Max=m
                    possibleGuess=[i[:] for i in optionList if   AdjustmentInverse(maxElement)==HowManyBc(item1[:],i[:])]
                    nextGuess=possibleGuess[0][:]
            guess=nextGuess[:]
            BC=HowManyBc(guess[:],secret[:])
            counter=counter+1
    

I get:

for [5, 3, 3, 4] counter is 7

for [5, 4, 4, 5] counter is 8

If someone could help I would appreciate it very much!

Thanks,mike


Answer: ### 1\. What's wrong with your implementation

There are four mistakes.

  1. 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".

  2. 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.

  3. 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!

  4. 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

  1. 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.

  2. 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`?)

  3. 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]
    

  4. 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`](http://docs.python.org/3/library/stdtypes.html#common-sequence-
operations) 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`](http://docs.python.org/3/library/collections.html#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

  1. Evaluating a guess (your function `HowManyBc`) can be reduced to just three lines using the class [`collections.Counter`](http://docs.python.org/3/library/collections.html#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](http://docs.python.org/3/library/doctest.html): these are a quick
way to simultaneously provide examples in the documentation and to test the
function.

  2. The function [`itertools.product`](http://docs.python.org/3/library/itertools.html#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)]
    

  3. Knuth's five-guess algorithm uses the [minimax principle](https://en.wikipedia.org/wiki/Minimax). So why not implement it by taking the [`min`](http://docs.python.org/3/library/functions.html#min) of a sequence of calls to [`max`](http://docs.python.org/3/library/functions.html#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)
    

