Mastermind solver in rust
Sun 17 March 2024
(Not mastermind) code breaking machine (Photo credit: wikipedia)
I recently watch a video [1] explaining how to solve mastermind. I wanted to try it myself, so I coded it in rust. Here are the code and the playground.
The game
I don't think this game needs explanation. Wikipedia provides more information.
The code
Let's divide our code in several steps and produce a quick and (not so) dirty code.
The board
- We need:
- colored pins (Color struct)
- a structure to represent a pattern (the Code)
- Pegs for the master to give hints to the guesser.
I implemented the Display trait for the Code to have a more compact representation than the Debug.
#[derive(Clone, Debug, Eq, PartialEq, Hash)]
enum Peg {
Correct,
Misplaced,
}
#[derive(Clone, Debug, Eq, PartialEq, Hash)]
enum Color {
Red,
Green,
Yellow,
Blue,
Purple,
White,
}
impl fmt::Display for Color {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
let c = match self {
Color::Red => "R",
Color::Green => "G",
Color::Yellow => "Y",
Color::Blue => "B",
Color::Purple => "P",
Color::White => "W",
};
write!(f, "{c}")
}
}
#[derive(Clone, Debug, Eq, PartialEq, Hash)]
struct Code(Vec<Color>);
impl fmt::Display for Code {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{}", self.0.iter().map(|c| format!("{}", c)).join(" "))
}
}
I added a possible random initialization for a Code
impl Code {
fn random() -> Self {
let mut rng = thread_rng();
let colors = vec![
Color::Red,
Color::Green,
Color::Yellow,
Color::Blue,
Color::Purple,
Color::White,
];
Self(
(0..4)
.map(|_| {
colors
.choose(&mut rng)
.expect("at least one color exist")
.clone()
})
.collect::<Vec<_>>(),
)
}
}
Hints
The Answer (set of Correct and Misplaced pegs) can be initiated from guess (given a guess and a solution, what is the hint the master must give?). To compute it, I used a 2 passes approach: on the first pass, I identify the correct colors and remove them (pins used) and on the second one, I identify the misplaced colors. I used this approach to be able to remove pins already used to compute the hint.
Minimax
The heart of the algorithm reside here. Given all the remaining possible answer (left, l.136) the algorithm must look for what can happen in the next step. In this next step, the guesser (code breaker) will obtain a hint. For all possible hint he can obtain, there will be some solutions left. The worse hint he can get is the one leaving the more remaining codes. The guesser must propose a code from those remaining codes in order to maximize the quantity of information received.
fn get_worse_solution<'a>(proposal: &'a Code, hint: &'a Answer, left: &HashSet<Code>) -> Code {
let left: HashSet<Code> = left
.iter()
.filter(|sol| Answer::from_guess(proposal, sol) == *hint)
.cloned()
.collect();
let mut ans = HashMap::new();
let possible_hints = get_all_hints();
for possible_hint in possible_hints {
ans.insert(
possible_hint.clone(),
get_possible_codes(proposal, &possible_hint, &left),
);
}
let worse_next_score = ans
.values()
.map(|v| v.len())
.max()
.expect("at least one value");
let worse_next_hint = ans
.iter()
.filter_map(|(k, v)| {
if v.len() == worse_next_score {
Some(k)
} else {
None
}
})
.next()
.expect("there should be at least one solution left");
ans[worse_next_hint]
.iter()
.next()
.expect("worse solution is greater than zero")
.clone()
}
Players
To play, I decided to implement 2 threads, one for the guesser, the other for the master. They communicate sending Code and Answer on dedicated channels. They also output some state. Their implementation is straight forward.
| [1] | Mastermind with Steve Mould, singing banana |
Category: maths Tagged: rust maths game game theory
_(cropped).jpg)
