Dan Q found GC33BAJ WWW#4 – earthcache.org

This checkin to GC33BAJ WWW#4 – earthcache.org reflects a geocaching.com log entry. See more of Dan's cache logs.

Geopup and I found quite easily while out on a walk. The excitable doggo isn’t so keen on stopping and searching for caches when there are so many new and exciting smells just over her visual horizon, so today’s expedition might only give me a couple of minutes to hunt for each: we’ll have to see if that’s enough to log any further finds this morning.

Dan Q performed maintenance for GC9Z37K Friar’s Farm – Far-Flung Fence

This checkin to GC9Z37K Friar's Farm - Far-Flung Fence reflects a geocaching.com log entry. See more of Dan's cache logs.

Found left out in clear with lid open but otherwise not vandalised. Closed and re-hid deeper into hiding place. Will add a geocaching information card on my next visit to better explain its presence to any muggles passing by.

Dan Q found GC5PPFT Ssssshhhh it’s a …….

This checkin to GC5PPFT Ssssshhhh it's a ....... reflects a geocaching.com log entry. See more of Dan's cache logs.

I’ve been working in Witney one day every week or two lately, but somehow I’ve never managed to sync up my work times with the hours that this building is accessible! Or, when I do, I’m in a hurry and don’t have time to stop and hunt!

This morning, though, the stars aligned and I was able to get to the GZ. The cache was pretty much where I expected based on the coordinates and the hint, but still took a minute out two to lay hands on. Soon, though, I was quietly sitting and reading past log entries.

SL TFTC! FP awarded for sheer awesome.

Dan sits in a library, holding a small book and with his finger to his lips in a 'shush' gesture. The back cover of the book contains text identifying it as a geocache.

×

Dan Q found GC8VQ92 Freeland to Hanborough 5

This checkin to GC8VQ92 Freeland to Hanborough 5 reflects a geocaching.com log entry. See more of Dan's cache logs.

The geopup and I took a slightly inelegant route down to the valley bottom after she insisted we try a steep route atop a carpet of dry, dusty leaves. Made it down intact, though, and found this cache in the very second hiding place we tried. TFTC!

Dan, wearing purple pyjama bottoms, a black t-shirt, and a black bandana, sits in a woodland setting with a dog who's just put herself off the bottom of the frame at the last second.

×

Dan Q couldn’t find GC8V4T3 Freeland to Hanborough 2

This checkin to GC8V4T3 Freeland to Hanborough 2 reflects a geocaching.com log entry. See more of Dan's cache logs.

A pair of walkers who’d stopped at the GZ for a snack made searching difficult, plus the geodog isn’t very good at stealth, so we had to give up on our search for this one. Maybe on the way back. (Although as I write this I see they’re coming the same direction as us; might need stealth again yet!)

.well-known/links in WordPress

Via Jeremy Keith I today discovered Jim Nielsen‘s suggestion for a website’s /.well-known/links to be a place where it can host a JSON-formatted list of all of its outgoing links.

That’s a really useful thing to have in this new age of the web, where Refererer: headers are no-longer commonly passed cross-domain and Google Search no longer provides the link: operator. If you want to know if I’ve ever linked to your site, it’s a bit of a drag to find out.

JSON output from DanQ.me's .well-known/links, showing 1,150 outbound links to en.wikipedia.org domains, for topics like "Bulls and Cows", "Shebang (Unix)", "Imposter syndrome", "Interrobang", and "Blakedown".
To nobody’s surprise whatsoever, I’ve made a so many links to Wikipedia that I might be single-handedly responsible for their PageRank.

So, obviously, I’ve written an implementation for WordPress. It’s really basic right now, but the source code can be found here if you want it. Install it as a plugin and run wp outbound-links to kick it off. It’s fast: it takes 3-5 seconds to parse the entirety of danq.me, and I’ve got somewhere in the region of 5,000 posts to parse.

You can see the results at https://danq.me/.well-known/links – if you’ve ever wondered “has Dan ever linked to my site?”, now you can find the answer.

If this could be useful to you, let’s collaborate on making this into an actually-useful plugin! Otherwise it’ll just languish “as-is”, which is good enough for my purposes.

Beating Children at Mastermind [Video]

This post is also available as an article. So if you'd rather read a conventional blog post of this content, you can!

This video accompanies a blog post of the same title. The content is basically the same – if you prefer videos, watch this video. If you prefer blog posts, go read the blog post. You might also like to play with my Mastermind solver or view the source code.

Also available on YouTube and Facebook.

Beating Children at Mastermind

This post is also available as a video. If you'd prefer to watch/listen to me talk about this topic, give it a look.

This blog post is also available as a video. Would you prefer to watch/listen to me tell you about how I’ve implemented a tool to help me beat the kids when we play Mastermind?

I swear that I used to be good at Mastermind when I was a kid. But now, when it’s my turn to break the code that one of our kids has chosen, I fail more often than I succeed. That’s no good!

Black, white, brown, blue, green, orange and yellow Mastermind pegs in a disordered heap.
If you didn’t have me pegged as a board gamer… where the hell have you been?

Mastermind and me

Maybe it’s because I’m distracted; multitasking doesn’t help problem-solving. Or it’s because we’re “Super” Mastermind, which differs from the one I had as a child in that eight (not six) peg colours are available and secret codes are permitted to have duplicate peg colours. These changes increase the possible permutations from 360 to 4,096, but the number of guesses allowed only goes up from 8 to 10. That’s hard.

A plastic Mastermind board in brown and green; it has twelve spots for guessing and shows six coloured pegs. The game has been won on the sixth guess.
The set I had as a kid was like this, I think. Photo courtesy ZeroOne; CC-BY-SA license.

Or maybe it’s just that I’ve gotten lazy and I’m now more-likely to try to “solve” a puzzle using a computer to try to crack a code using my brain alone. See for example my efforts to determine the hardest hangman words and make an adverserial hangman game, to generate solvable puzzles for my lock puzzle game, to cheat at online jigsaws, or to balance my D&D-themed Wordle clone.

Hey, that’s an idea. Let’s crack the code… by writing some code!

Screenshot showing Mastermind game from WebGamesOnline.com. Seven guesses have been made, each using only one colour for each of the four pegs, and no guesses are corect; only red pegs have never been guessed.
This online edition plays a lot like the version our kids play, although the peg colours are different. Next guess should be an easy solve!

Representing a search space

The search space for Super Mastermind isn’t enormous, and it lends itself to some highly-efficient computerised storage.

There are 8 different colours of peg. We can express these colours as a number between 0 and 7, in three bits of binary, like this:

Decimal Binary Colour
0 000 Red
1 001 Orange
2 010 Yellow
3 011 Green
4 100 Blue
5 101 Pink
6 110 Purple
7 111 White

There are four pegs in a row, so we can express any given combination of coloured pegs as a 12-bit binary number. E.g. 100 110 111 010 would represent the permutation blue (100), purple (110), white (111), yellow (010). The total search space, therefore, is the range of numbers from 000000000000 through 111111111111… that is: decimal 0 through 4,095:

Decimal Binary Colours
0 000000000000 Red, red, red, red
1 000000000001 Red, red, red, orange
2 000000000010 Red, red, red, yellow
…………
4092 111111111100 White, white, white, blue
4093 111111111101 White, white, white, pink
4094 111111111110 White, white, white, purple
4095 111111111111 White, white, white, white

Whenever we make a guess, we get feedback in the form of two variables: each peg that is in the right place is a bull; each that represents a peg in the secret code but isn’t in the right place is a cow (the names come from Mastermind’s precursor, Bulls & Cows). Four bulls would be an immediate win (lucky!), any other combination of bulls and cows is still valuable information. Even a zero-score guess is valuable- potentially very valuable! – because it tells the player that none of the pegs they’ve guessed appear in the secret code.

A plastic Mastermind board in blue and yellow with ten guess spaces and eight pegs. The sixth guess is unscored but looks likely to be the valid solution.
If one of Wordle‘s parents was Scrabble, then this was the other. Just ask its Auntie Twitter.

Solving with Javascript

The latest versions of Javascript support binary literals and bitwise operations, so we can encode and decode between arrays of four coloured pegs (numbers 0-7) and the number 0-4,095 representing the guess as shown below. Decoding uses an AND bitmask to filter to the requisite digits then divides by the order of magnitude. Encoding is just a reduce function that bitshift-concatenates the numbers together.

116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
/**
 * Decode a candidate into four peg values by using binary bitwise operations.
 */
function decodeCandidate(candidate){
  return [
    (candidate & 0b111000000000) / 0b001000000000,
    (candidate & 0b000111000000) / 0b000001000000,
    (candidate & 0b000000111000) / 0b000000001000,
    (candidate & 0b000000000111) / 0b000000000001
  ];
}

/**
 * Given an array of four integers (0-7) to represent the pegs, in order, returns a single-number
 * candidate representation.
 */
function encodeCandidate(pegs) {
  return pegs.reduce((a, b)=>(a << 3) + b);
}

With this, we can simply:

  1. Produce a list of candidate solutions (an array containing numbers 0 through 4,095).
  2. Choose one candidate, use it as a guess, and ask the code-maker how it scores.
  3. Eliminate from the candidate solutions list all solutions that would not score the same number of bulls and cows for the guess that was made.
  4. Repeat from step #2 until you win.

Step 3’s the most important one there. Given a function getScore( solution, guess ) which returns an array of [ bulls, cows ] a given guess would score if faced with a specific solution, that code would look like this (I’m convined there must be a more-performant way to eliminate candidates from the list with XOR bitmasks, but I haven’t worked out what it is yet):

164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
/**
 * Given a guess (array of four integers from 0-7 to represent the pegs, in order) and the number
 * of bulls (number of pegs in the guess that are in the right place) and cows (number of pegs in the
 * guess that are correct but in the wrong place), eliminates from the candidates array all guesses
 * invalidated by this result. Return true if successful, false otherwise.
 */
function eliminateCandidates(guess, bulls, cows){
  const newCandidatesList = data.candidates.filter(candidate=>{
    const score = getScore(candidate, guess);
    return (score[0] == bulls) && (score[1] == cows);
  });
  if(newCandidatesList.length == 0) {
    alert('That response would reduce the candidate list to zero.');
    return false;
  }
  data.candidates = newCandidatesList;
  chooseNextGuess();
  return true;
}

I continued in this fashion to write a full solution (source code). It uses ReefJS for component rendering and state management, and you can try it for yourself right in your web browser. If you play against the online version I mentioned you’ll need to transpose the colours in your head: the physical version I play with the kids has pink and purple pegs, but the online one replaces these with brown and black.

Testing the solution

Let’s try it out against the online version:

As expected, my code works well-enough to win the game every time I’ve tried, both against computerised and in-person opponents. So – unless you’ve been actively thinking about the specifics of the algorithm I’ve employed – it might surprise you to discover that… my solution is very-much a suboptimal one!

A young boy sits cross-legged on the floor, grinning excitedly at a Mastermind board (from the code-maker's side).
My code has only failed to win a single game… and that turned out to because my opponent, playing overexcitedly, cheated in the third turn. To be fair, my code didn’t lose either, though: it identified that a mistake must have been made and we declared the round void when we identified the problem.

My solution is suboptimal

A couple of games in, the suboptimality of my solution became pretty visible. Sure, it still won every game, but it was a blunt instrument, and anybody who’s seriously thought about games like this can tell you why. You know how when you play e.g. Wordle (but not in “hard mode”) you sometimes want to type in a word that can’t possibly be the solution because it’s the best way to rule in (or out) certain key letters? This kind of strategic search space bisection reduces the mean number of guesses you need to solve the puzzle, and the same’s true in Mastermind. But because my solver will only propose guesses from the list of candidate solutions, it can’t make this kind of improvement.

Animation showing how three clues alone are sufficient to derive a unique answer from the search space of the original "break into us" lock puzzle.
My blog post about Break Into Us used a series of visual metaphors to show search space dissection, including this one. If you missed it, it might be worth reading.

Search space bisection is also used in my adverserial hangman game, but in this case the aim is to split the search space in such a way that no matter what guess a player makes, they always find themselves in the larger remaining portion of the search space, to maximise the number of guesses they have to make. Y’know, because it’s evil.

Screenshot showing a single guess row from Online Mastermind, with the guess Red, Red, Green, Green.
A great first guess, assuming you’re playing against a random code and your rules permit the code to have repeated colours, is a “1122” pattern.

There are mathematically-derived heuristics to optimise Mastermind strategy. The first of these came from none other than Donald Knuth (legend of computer science, mathematics, and pipe organs) back in 1977. His solution, published at probably the height of the game’s popularity in the amazingly-named Journal of Recreational Mathematics, guarantees a solution to the six-colour version of the game within five guesses. Ville [2013] solved an optimal solution for a seven-colour variant, but demonstrated how rapidly the tree of possible moves grows and the need for early pruning – even with powerful modern computers – to conserve memory. It’s a very enjoyable and readable paper.

But for my purposes, it’s unnecessary. My solver routinely wins within six, maybe seven guesses, and by nonchalantly glancing at my phone in-between my guesses I can now reliably guess our children’s codes quickly and easily. In the end, that’s what this was all about.

× × × × × ×