Building a Mastermind AI

Lachlan Gibson
Lachlan Gibson

This is a work in progress. Remaining tasks:

  • Add game logic to allow duplicate colours
  • Improve UI
    • Beautify settings section
    • Possibly add drag and drop functionality for pegs
  • Write article explaining the game and AI
    • Explain the game
    • Explain the various types of AI approaches
    • Run experiments to compare AI performance
  • Publish code and experimental results to GitHub
Guess 1/12

Remaining options: 360

NOTES

If the code size is kk, then the set of possible keys is

K={(kr,kw)∈Z⩾02 ∣ kr+kw⩽K}\mathcal{K}=\{(k_r,k_w)\in\Z_{\geqslant 0}^2 ~|~ k_r + k_w \leqslant K\}

The total number of unique keys is then

∣K∣=(K+1)(K+2)2|\mathcal{K}| = \frac{(K+1)(K+2)}{2}

For any given guess from the set of valid guesses, G\mathcal{G}, we can partition the set of possible codes, P⊆G\mathcal{P}\subseteq\mathcal{G}, into upto ∣K∣|\mathcal{K}| nonempty mutually disjoint subsets, Tk(P,g)⊆P\mathcal{T}_k(\mathcal{P},g)\subseteq\mathcal{P}, where k∈Kk\in\mathcal{K}. This gives us the framework to consider some myopic strategies by using greedy algorithms, which optimise the current turn without considering future turns.

The first greedy algorthm would be to choose the guess that minimizes the maximum number of possible codes after the result is known, thereby mitigating the worst case scenario of the next turn.

arg min⁡g∈Gmax⁡k∈K∣T(P,g,k)∣\argmin_{g\in\mathcal{G}}\max_{k\in\mathcal{K}}|\mathcal{T}(\mathcal{P},g,k)|

Another greedy algorithm would be to choose the guess that minimises the expected number of possible codes after the key is known. This could result in a better average performance over multiple games. If all codes are equally likely then the probability of each key is the size of the corresponding subset divided by the total number of possible codes.

arg min⁡g∈G1∣P∣∑k∈K∣T(P,g,k)∣2\argmin_{g\in\mathcal{G}}\frac{1}{|\mathcal{P}|}\sum_{k\in\mathcal{K}}|\mathcal{T}(\mathcal{P},g,k)|^2

In practice the factor of ∣P∣|\mathcal{P}| can be omitted as it is constant for all guesses.

In many cases it can happen that multiple guesses are equally optimal according to these greedy metrics. Ties can be broken arbitrarily by choosing the first, last or a random guess from the set of equally greedily optimal guesses. Possibly a better approach would be to use another greedy metric to break the tie. This is lexicographic optimisation. In fact, these two greedy metrics are from the same class. Consider the metric which minimises the expected size of the next partition raised to the power of ll.

Tl∗=min⁡g∈G∑k∈K∣T(P,g,k)∣l+1T_l^*=\min_{g\in\mathcal{G}}\sum_{k\in\mathcal{K}}|\mathcal{T}(\mathcal{P},g,k)|^{l+1}