Code cleanup for the New Year

By: Blog by Bogumił Kamiński

Re-posted from: https://bkamins.github.io/julialang/2024/01/05/mastermind.html

Introduction

I have done a small cleanup of my folders with code for the New Year.
In the process I have discovered some old Julia code that I have written and forgotten about.
One of such scripts is a simple Mastermind solver.
So I decided to share it in this post.

The code was tested under Julia 1.10.0, Combinatorics.jl 1.0.2, FreqTables.jl 0.4.6, and StatsBase.jl 0.34.2.

The Mastermind game

I assume you know how Mastermind is played.
If not – I recommend you read the Wikipedia description before continuing.

Let me briefly summarize the version of the game that I used as a reference
(this is a version that was popular in Poland when I was young):

  • The game is played using 8 colors of pegs.
  • The code that we are required to break (a solution) consists of 5 pegs of which each has to have a different color.
  • You are allowed to guess the solution by showing 5 pegs (that also have to be of different colors)
    and you get two numbers: black representing number of pegs matching color and position between your guess and a solution,
    and white dots representing pegs that have a correct color, but wrong position.
  • The game is finished when your guess matches the solution (i.e. you get 5 blacks and 0 whites).
    The outcome of the game is the number of guesses you have made.

The problem

In my code I wanted to compare two strategies. Both of them use a concept of available options,
so let us define it first.

First note that we have 5 pegs and each of them has one of 8 unique colors that we have:

julia> binomial(8, 5) * factorial(5)
6720

initially available options as solution when we start a game. After each move we can check which of options
match the responses to your guesses. This matching reduces the number of available options.

The first strategy we will consider is to randomly pick a guess that is still an available option.
This strategy is in practice possible to follow (up to ensuring randomness of choice which can be hard :))
even without the help of the computer. At any moment during the game you just need to show a guess that
is consistent with the answers you already got.

The second strategy, called minimax, works as follows. Before making a move we consider every initially
available option as a possible candidate. For each candidate we check what black-white combination
we would get against all available options. From this we can get a distribution of number of black-white
combinations that a given guess would produce. We sort this distribution in a descending order and pick
the guess that produces the lexicographically smallest value.

Let me explain this by example. Assume we consider guesses A, B, and C and have still 20 available options.

For the guess A we count that we could have 10 answers of the form 2 black & 2 white, 5 answers 1 black & 2 white,
and 5 answers 2 black & 1 white. Thus for option A the encoding is [10, 5, 5].

For the guess B we count that we could have 3 answers of the form 2 black & 3 white, 5 answers 1 black & 2 white,
and 12 answers 2 black & 1 white. Thus for option B the encoding is [12, 5, 3].

For the guess C we count that we could have 10 answers of the form 1 black & 1 white, 8 answers 2 black & 2 white,
and 2 answers 1 black & 1 white. Thus for option C the encoding is [10, 8, 2].

Therefore since lexicographically [10, 5, 5] < [10, 8, 2] < [12, 5, 3] the option A is best (and we would pick it)
and the option B is worst.

The rationale behind this strategy is that we want to minimize the maximum possible number of available options we will be
left with in the next round.

Clearly minimax strategy is much more complex. For sure it is hard to be used without computer assistance. The question is
if it is better than random strategy and, if so, by how much.

The code

Let us start with the code that implements the game.

The first part is environment setup:

using Combinatorics
using FreqTables
using Random
using StatsBase

struct Position
    pos::NTuple{5, Int8}
    pegs::NTuple{8, Bool}
end

const ALL_POSITIONS = let
    combs = combinations(Int8.(1:8), 5)
    perms = reduce(vcat, (collect∘permutations).(combs))
    [Position(Tuple(pos), ntuple(i -> i in pos, 8)) for pos in perms]
end

In this part of code we loaded all required packages. Next we define Position structure.
It encodes the colors (as values from 1 to 8) passed for each peg. The pos field
directly encodes the position. The pegs field is a helper code containing information
if a given color was used in pos (to make it simpler to later use this data structure).
Finally we create ALL_POSITIONS vector which contains all 6720 available options at the start of the game.

Next define a function counting the number of black and white matches between the guess and the solution:

function match(p1::Position, p2::Position)
    pos1, pegs1 = p1.pos, p1.pegs
    pos2, pegs2 = p2.pos, p2.pegs
    black = sum(x -> x[1] == x[2], zip(p1.pos, p2.pos))
    matches = sum(x -> x[1] & x[2], zip(p1.pegs, p2.pegs))
    return black, matches - black
end

Here we see why both pos and pegs values are useful. We use pos to compute the number of black matches.
Then we use pegs to compute the number of all matches (disregarding the location). Therefore matches - black
gives ut the number of white matches.

We are now ready to implement our decision rule functions:

random_rule(options::AbstractVector{Position}) = rand(options)

function minimax_rule(options::AbstractVector{Position})
    length(options) == 1 && return only(options)
    best_guess = options[1]
    best_guess_lengths = [length(options)]
    for guess in shuffle(options)
        states = Dict{Tuple{Int,Int},Int}()
        for opt in options
            resp = match(guess, opt)
            states[resp] = get(states, resp, 0) + 1
        end
        current_guess_lengths = sort!(collect(values(states)), rev=true)
        if current_guess_lengths < best_guess_lengths
            best_guess = guess
            best_guess_lengths = current_guess_lengths
        end
    end
    return best_guess
end

The random_rule is simple. We just randomly pick one of the available options.

The minimax_rule code is more complex. We traverse guess taken from options in random order.
For each guess in the states dictionary we keep the count of black-white answers generated by
this guess. Then current_guess_lengths keeps the vector of combination counts sorted in a descending order.
After checking all guess values we return the best_guess value which holds the guess with the smallest value of
current_guess_lengths.

The final part of the code is a rule testing function:

function run_test(rule::Function, solution::Position)
    options = ALL_POSITIONS
    moves = 0
    while true
        moves += 1
        guess::Position = rule(options)
        guess == solution && return moves
        resp = match(guess, solution)
        options = filter(opt -> match(guess, opt) == resp, options)
        @assert solution in options
    end
end

In the run_test we get the rule function and the solution to the game. Next iteratively we ask the rule function what next move it picks. If it is the solution
then we return the number of moves taken. Otherwise we filter the available options, stored in the options variable to leave only those that match the responses
received by matching the guess against the solution.

Now the big question is if the extra complexity of minimax_rule is worth the effort?

The test

Now we are ready to test the random_rule against the minimax_rule. One important observation that we can make is that it is enough to run the run_test function
with only one starting solution, which I pick to be ALL_OPTIONS[1]. The reason is that the problem is fully symmetric (i.e. all possible solutions are indistinguishable with respect to recoloring)
and both random_rule and minimax_rule are fully randomized. For random_rule it is clear. For minimax_rule the key line of code that ensures it is for guess in shuffle(options).
In this way we ensure that we do not favor any options. E.g. if we did for guess in options then clearly we would favor options[1] option (as the game would always finish in the first move).

Now let us run the tests:

julia> Random.seed!(1234);

julia> @time random_res = [run_test(random_rule, ALL_POSITIONS[1]) for i in 1:1_000_000];
138.395938 seconds (7.13 M allocations: 97.072 GiB, 1.59% gc time, 0.11% compilation time)

julia> @time minimax_res = [run_test(minimax_rule, ALL_POSITIONS[1]) for i in 1:1_000];
1162.463279 seconds (65.08 M allocations: 20.119 GiB, 0.03% gc time, 0.04% compilation time)

As you can see I run one thousand times more random_rule than minimax_rule as the former is much faster (and still ten times more time is spent in gathering the results for minimax_rule).

Now let us collect some statistics about the both approaches to the solution:

julia> proptable(random_res)
9-element Named Vector{Float64}
Dim1  │
──────┼─────────
1     │ 0.000156
2     │ 0.002364
3     │  0.02251
4     │ 0.139851
5     │  0.39269
6     │ 0.350372
7     │  0.08736
8     │ 0.004646
9     │   5.1e-5

julia> proptable(minimax_res)
6-element Named Vector{Float64}
Dim1  │
──────┼──────
3     │ 0.015
4     │ 0.138
5     │ 0.476
6     │ 0.336
7     │ 0.034
8     │ 0.001

Note that the probability of solving the puzzle in one move is (we hit the solution by chance):

julia> 1 / (binomial(8, 5) * factorial(5))
0.00014880952380952382

It is pretty accurately approximated for random_res. For minimax_res we did not get even one such observation because our sample was too small.
In general, what we can see is that the probabilities of numbers of moves are similar (keeping in mind the fact that minimax_res has only 1000 observations),
except that random rule less frequently finishes in 5 moves, and more frequently in 7 moves. However, the difference is not very large.
This is also reflected by the fact that the mean time required to finish the game is only slightly lower for minimax strategy:

julia> mean(random_res)
5.346647

julia> mean(minimax_res)
5.239

Conclusions

Interestingly, for the variant of Mastermind we considered a random strategy is not much worse than a much more expensive minimax approach.
A limitation of our minimax approach is that it is doing only one-step-ahead optimization. As an extension to our exercise you could consider
checking how much better would be a full-depth minimax algorithm.

Happy hacking!