Master Mind, Part 2
November 20, 2009
We can calculate the maximum score for a given pool and probe like this:
(define (max-score pool probe)
(apply max (map cdr
(uniq-c string=? (sort string<?
(map (lambda (p) (score p probe)) pool))))))
Then the minimax probe is determined by computing the maximum score over all possible probes, selecting the minimum. The tricky
if implements Knuth’s “subject-to” requirement; if the probe is a new minimum, or if it equal to the current minimum, is a member of the pool, and the current minimum is not a member of the pool, keep it as the new minimum, otherwise loop to the next probe.
(define (minimax pool)
(let loop ((min-probe '()) (min-size #e1e10) (ps probes))
(if (null? ps) min-probe
(let ((size (max-score pool (car ps))))
(if (or (< size min-size)
(and (= size min-size)
(member (car ps) pool)
(not (member min-probe pool))))
(loop (car ps) size (cdr ps))
(loop min-probe min-size (cdr ps)))))))
The other thing that we need before we can write the solver is a way to apply the result of a probe to the current pool, producing a new, smaller pool:
(define (apply-probe pool probe result)
(filter (lambda (p) (string=? (score p probe) result)) pool))
Note that none of the functions shown above take the code word as an argument; there is no cheating! The solver needs to know the code word, of course, so it can determine the score for each probe:
(define (solver . args)
(let ((code (if (pair? args) (car args) (fortune probes))))
(let loop ((n 1) (pool probes))
(let* ((probe (minimax pool))
(result (score code probe)))
(display probe) (display " ")
(display result) (newline)
(if (string=? (make-string num-pegs #\B) result) n
(loop (+ n 1) (apply-probe pool probe result)))))))
As with the setter, the solver can either be given a code word or choose one at random. Here is a sample interaction with the solver:
> (solver '(3 6 3 2))
(1 1 2 2) B...
(1 3 4 4) W...
(3 5 2 6) BWW.
(1 4 6 2) BW..
(3 6 3 2) BBBB
The initial pool has 1296 entries. After the first probe, 1 1 2 2, there are 256 entries left, the second probe, 1 3 4 4, reduces the pool to 44 entries, the third probe, 3 5 2 6, reduces the pool to seven entries, and the fourth probe, 1 4 6 2, distinguishes between them. After the third probe, the seven entries in the pool are 3 6 3 2, 3 6 6 2, 4 5 6 2, 4 6 2 5, 5 5 3 2, 6 4 2 5, and 6 6 2 3. Note that none of those seven entries could distinguish the winner; the fourth probe, 1 4 6 2, comes from outside the current pool, demonstrating Knuth’s “subject to” rule.
The solver works equally well with eight colors and five pegs, though the large increase in the size of the search space, to 85 = 32768 possible codes, makes it slow:
> (solver '(3 6 3 2 1))
(1 1 2 3 4) WWW..
(2 2 5 4 3) WW...
(3 6 6 1 2) BBWW.
(3 6 7 2 1) BBBB.
(3 6 3 2 1) BBBBB
solver returns the number of probes, we can study its behavior. It takes 5801 probes to solve each possible puzzle once, an average of 4.476 probes per puzzle:
(let loop ((n 0) (ps probes))
(if (null? ps) n
(loop (+ n (solver (car ps))) (cdr ps))))
Knuth’s algorithm minimizes the worst-case solution in five probes. By comparison, Koyama and Loi give two algorithms that improve the average number of probes in their article “An Optimal Mastermind Strategy” in the Journal of Recreational Math. Volume 25, pages 251-256, 1993 (not available online); one algorithm uses 4.430 probes on average, but has a worst-case of six probes, the other uses 4.431 probes on average with a worst-case of five probes.
We re-used all the code from the previous exercise, and range, fold-right, make-list, filter, sum, uniq-c, rand, sort and cross from the Standard Prelude. The code is collected at http://programmingpraxis.codepad.org/tHXIIIfF, but you can’t run it, because it causes a timeout.
Pages: 1 2